Uma Segment Tree é uma estrutura de dados do tipo árvore binária, projetada para particionar intervalos em subintervalos unitários. Cada folha corresponde a um elemento da sequência original, facilitando operações eficientes em intervalos específicos. Essa estrutura permite consultas em O(log N), tornando-a ideal para problemas que envolvem buscas em faixas de dados.

Princípios de Funcionamento

A Segment Tree utiliza divisão binária recursiva para dividir um inetrvalo maior em dois subintervalos menores, construindo uma árvore balanceada. O nó raiz representa o intervalo completo, e as folhas armazenam informações individuais. Essa abordagem suporta operações como:

• Consultas em intervalos: Obter agregações como soma, máximo ou mínimo dentro de uma faixa especificada.
• Atualizações em intervalos: Modificar valores em uma faixa inteira, por exemplo, adicionando um valor constante a todos os elementos.
• Manutenção dinâmica: Atualizar automaticamente as informações quando os dados subjacentes mudam, sem reconstruir a estrutura.

Representação em Memória

Na implementação comum, a Segment Tree é armazenada em um array. O nó raiz ocupa o índice 0. Para um nó no índice i, o filho esquerdo está em 2*i+1 e o filho direito em 2*i+2. Essa representação compacta facilita o acesso e a manipulação eficiente.

Implementação em C++

Inserção de Valores

// Insere um valor na Segment Tree, atualizando contadores ao longo do caminho
void inserir_valor(vector<int>& arvore, int no, int inicio, int fim, int valor) {
    arvore[no]++;
    if (inicio == fim) return;
    int meio = (inicio + fim) / 2;
    int esquerda = no * 2 + 1;
    int direita = no * 2 + 2;
    if (valor <= meio) {
        inserir_valor(arvore, esquerda, inicio, meio, valor);
    } else {
        inserir_valor(arvore, direita, meio + 1, fim, valor);
    }
}</int>

Busca em Inetrvalos

// Retorna o valor associado a um ponto específico na Segment Tree
int buscar_valor(const vector<int>& arvore, int no, int inicio, int fim, int valor) {
    if (inicio == fim) return arvore[no];
    int meio = (inicio + fim) / 2;
    int esquerda = no * 2 + 1;
    int direita = no * 2 + 2;
    if (valor <= meio) {
        return buscar_valor(arvore, esquerda, inicio, meio, valor);
    } else {
        return buscar_valor(arvore, direita, meio + 1, fim, valor);
    }
}</int>

Exibição da Estrutura

// Imprime os nós da Segment Tree em ordem de travessia
void exibir_arvore(const vector<int>& arvore, int no, int inicio, int fim) {
    cout << "[" << inicio << " " << fim << "] nó " << no << " = " << arvore[no] << endl;
    if (inicio == fim) return;
    int meio = (inicio + fim) / 2;
    exibir_arvore(arvore, no * 2 + 1, inicio, meio);
    exibir_arvore(arvore, no * 2 + 2, meio + 1, fim);
}</int>