Visão Geral da Árvore de Segmentos

A Árvore de Segmentos é uma estrutura de dados versátil e poderosa, projetada para realizar operações de consulta e modificação em intervalos de um array. A sua principal vantagem reside na capacidade de executar essas operações com complexidade de tempo de O(log n). Cada nó na árvore armazena informações agregadas sobre um intervalo específico [start, end]. O nó raiz representa o intervalo completo, e cada nó pai possui dois filhos que dividem o intervalo do pai em duas metades estritamente adjacentes: [start, mid] e [mid + 1, end].

Armazenamento e Relações de Nós

Para otimizar o desempenho e a locality de cache, a árvore de segmentos é geralmente implementada utilizando um array linear, aproveitando a propriedade de ser uma árvore binária quase completa. As relações entre pais e filhos seguem a mesma lógica de uma heap binária:

• Filho esquerdo: node << 1 (equivalente a node * 2)
• Filho direito: node << 1 | 1 (equivalente a node * 2 + 1)

Para garantir que não haja estouro de buffer, o array que armazena os nós deve ter um tamanho de pelo menos 4 * N, onde N é o número de elementos no array original. Isso ocorre porque a árvore binária pode ter até 2N - 1 nós nos níveis superiores e até 2N nós no nível mais profundo, totalizando aproximadamente 4N nós.

struct SegmentTreeNode {
    int start, end;
    long long sum;
    long long max_val;
    long long lazy_add;
    long long lazy_mul;
};

const int MAXN = 100005;
SegmentTreeNode tree[MAXN * 4];

Construção da Árvore (Build)

A construção da árvore é um processo recursivo que inicializa os nós folha com os valores do array original e, em seguida, agrega as informações para os nós pais. A árvore é estática em relação ao seu tamanho; o intervalo total deve ser definido no momento da construção.

void pull(int node) {
    tree[node].sum = tree[node << 1].sum + tree[node << 1 | 1].sum;
    tree[node].max_val = max(tree[node << 1].max_val, tree[node << 1 | 1].max_val);
}

void build_tree(int node, int start, int end, const vector<int>& arr) {
    tree[node].start = start;
    tree[node].end = end;
    tree[node].lazy_add = 0;
    tree[node].lazy_mul = 1;
    
    if (start == end) {
        tree[node].sum = arr[start];
        tree[node].max_val = arr[start];
        return;
    }
    
    int mid = start + (end - start) / 2;
    build_tree(node << 1, start, mid, arr);
    build_tree(node << 1 | 1, mid + 1, end, arr);
    pull(node);
}

Propagação de Atualizações (Pull e Push)

A função pull (já demonstrada acima) atualiza um nó pai com base nos valores atuais de seus filhos. Já a função push (propagação preguiçosa ou lazy propagation) é responsável por transferir as atualizações pendentes de um nó pai para seus filhos. Isso é crucial para manter a complexidade O(log n) em atualizações de intervalo.

Quando múltiplas operações preguiçosas coexistem (como multiplicação e adição), a ordem de aplicação é estritamente primeiro multiplicar, depois adicionar. Matematicamente, se um valor x sofre uma multiplicação por m e depois uma adição de a, o resultado é x * m + a. Se uma nova multiplicação k for aplicada, a expressão torna-se (x * m + a) * k = x * (m * k) + (a * k).

void apply_lazy(int node, long long mul, long long add) {
    int length = tree[node].end - tree[node].start + 1;
    
    tree[node].sum = tree[node].sum * mul + add * length;
    tree[node].max_val = tree[node].max_val * mul + add;
    
    tree[node].lazy_mul *= mul;
    tree[node].lazy_add = tree[node].lazy_add * mul + add;
}

void push(int node) {
    if (tree[node].lazy_mul != 1 || tree[node].lazy_add != 0) {
        apply_lazy(node << 1, tree[node].lazy_mul, tree[node].lazy_add);
        apply_lazy(node << 1 | 1, tree[node].lazy_mul, tree[node].lazy_add);
        
        tree[node].lazy_mul = 1;
        tree[node].lazy_add = 0;
    }
}

Modificação de Intervalo

A atualização de intervalo utiliza a propagação preguiçosa para evitar a modificação nó por nó. Se o intervalo do nó atual estiver cmopletamente contido no intervalo de atualização, a marcação preguiçosa é aplicada diretamente. Caso contrário, as marcações são propagadas para os filhos (push) e a recursão continua.

void update_range(int node, int left, int right, long long mul, long long add) {
    if (left <= tree[node].start && tree[node].end <= right) {
        apply_lazy(node, mul, add);
        return;
    }
    
    push(node);
    int mid = tree[node].start + (tree[node].end - tree[node].start) / 2;
    
    if (left <= mid) update_range(node << 1, left, right, mul, add);
    if (right > mid) update_range(node << 1 | 1, left, right, mul, add);
    
    pull(node);
}

Consulta de Intervalo

A consulta segue uma lógica de divisão e conquista. É fundamental executar push antes de acessar os filhos para garantir que os valores consultados reflitam todas as atualizações pendentes.

SegmentTreeNode query_range(int node, int left, int right) {
    if (left <= tree[node].start && tree[node].end <= right) {
        return tree[node];
    }
    
    push(node);
    int mid = tree[node].start + (tree[node].end - tree[node].start) / 2;
    
    if (right <= mid) return query_range(node << 1, left, right);
    if (left > mid) return query_range(node << 1 | 1, left, right);
    
    SegmentTreeNode left_res = query_range(node << 1, left, right);
    SegmentTreeNode right_res = query_range(node << 1 | 1, left, right);
    
    SegmentTreeNode res;
    res.sum = left_res.sum + right_res.sum;
    res.max_val = max(left_res.max_val, right_res.max_val);
    return res;
}

Técnicas Avançadas

Árvore de Segmentos para Otimização de Grafos

Em problemas de caminhos mais curtos onde as arestas conectam um nó a um intervalo de nós (ou vice-versa), construir arestas individuais resultaria em complexidade O(N^2). A árvore de segmantos pode ser usada para criar nós virtuais que representam intervalos, reduzindo o número de arestas para O(N log N) e permitindo o uso de algoritmos como Dijkstra de forma eficiente.

Busca Binária na Árvore de Segmentos

É possível realizar buscas binárias diretamente na estrutura da árvore para encontrar, por exemplo, o primeiro índice em um intervalo [left, right] onde o valor seja maior que X. Isso reduz a complexidade de O(log^2 n) (busca binária externa + consulta na árvore) para O(log n).

A lógica consiste em podar ramos onde o valor máximo é menor ou igual a X e priorizar a subárvore esquerda para encontrar a primeira ocorrência (limite esquerdo).

int find_first_greater(int node, int left, int right, long long x) {
    // Poda: se o max_val do nó não atende ao critério, não há solução nesta subárvore
    if (tree[node].max_val <= x) return -1;
    
    // Caso base: nó folha
    if (tree[node].start == tree[node].end) return tree[node].start;
    
    // Se o nó atual está totalmente dentro do intervalo de consulta, desce binariamente
    if (left <= tree[node].start && tree[node].end <= right) {
        push(node);
        if (tree[node << 1].max_val > x) {
            return find_first_greater(node << 1, left, right, x);
        }
        return find_first_greater(node << 1 | 1, left, right, x);
    }
    
    // Sobreposição parcial: continua a divisão normal do intervalo
    push(node);
    int mid = tree[node].start + (tree[node].end - tree[node].start) / 2;
    int res = -1;
    
    if (left <= mid) {
        res = find_first_greater(node << 1, left, right, x);
    }
    if (res == -1 && right > mid) {
        res = find_first_greater(node << 1 | 1, left, right, x);
    }
    
    return res;
}

A verificação tree[node].max_val <= x no início da função é obrigatória. Ela não apenas garante a corretude da resposta, mas também previne que a complexidade degenere para O(log^2 n) ao evitar descidas desnecessárias em subárvores que não contêm a resposta.

Erros Comuns e Soluções

• Memory Limit Exceeded (MLE): Ocorre frequentemente quando os índices de consulta ou atualização excedem os limites definidos na construção da árvore (menores que 1 ou maiores que N), causando acesso a posições não alocadas no array. Valide sempre os limites de entrada.
• Runtime Error (RE) / Stack Overflow: Geralmente causado por condições de parada incorretas na recursão, resultando em loops infinitos e estouro de pilha. Verifique se as condições left <= mid e right > mid estão corretas e se o caso base (start == end) está sendo atingido.
• Reutilização da Estrutura: Ao processar múltiplos casos de teste, reutilizar a mesma árvore exige a redefinição completa dos valores e das marcas preguiçosas (lazy tags). O intervalo base [1, N] não pode ser alterado dinamicamente sem reconstruir a árvore.