Published

25/05/2026

Modified

22/04/2026

Estruturas: Árvores Segmentadas (SegTree)

Metáfora e Motivação

Você é díficil de agradar. Quando precisa realizar milhares de buscas em intervalos contínuos de um vetor (ex: somar tudo da cidade \(L\) até a cidade \(R\)), os Prefix Sums (Soma de Prefixos) te atendem. Porém, se o prefeito decide alterar ativamente o valor da cidade \(i\), a sua matriz de prefixos precisa ser destruida e refeita por completo.

  • Vetor ingênuo: Mudar valor na cidade \(i \rightarrow \mathcal{O}(1)\). Somar de \(L\) a \(R \rightarrow \mathcal{O}(N)\).
  • Somas de Prefixo: Somar de \(L\) a \(R \rightarrow \mathcal{O}(1)\). Mudar valor \(\rightarrow \mathcal{O}(N)\).
  • Árvore Segmentada: Somar de \(L\) a \(R \rightarrow \mathcal{O}(\log N)\). Mudar o valor \(\rightarrow \mathcal{O}(\log N)\).

A SegTree é o meio termo perfeito que funde a flexibilidade tática das atualizações locais dinâmicas com buscas agupadas.

Visualizando o Engessamento Segmentado

A lógica é estocar dados não apenas atomicamente (folhas), mas criar baldes com resumos. O Nó 0 guarda o resumo total (Posição 0 até a 7). Ele se divide sempre no meio.

Algoritmo OOP em C++

Diferente das PDs comuns, estruturas complexas pedem alocação orientada a Classe ou Estruturas limpas para evitar misturar indíces. Esse bloco computa as operações clássicas de Update de Ponto e Soma em Intervalo (“Range Query”):

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class SegTree {
private:
    vector<int> tree;
    int n;

    // Constrói O(N) inicialmente
    void build(const vector<int>& arr, int node, int esq, int dir) {
        if (esq == dir) {
            tree[node] = arr[esq];
        } else {
            int meio = esq + (dir - esq) / 2;
            build(arr, 2 * node, esq, meio);
            build(arr, 2 * node + 1, meio + 1, dir);
            // SOMA (Pode ser Trocado por Max, Min, GCD)
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    void update(int node, int esq, int dir, int pos_array, int novo_valor) {
        if (esq == dir) {
            tree[node] = novo_valor;
        } else {
            int meio = esq + (dir - esq) / 2;
            if (pos_array <= meio) {
                update(2 * node, esq, meio, pos_array, novo_valor);
            } else {
                update(2 * node + 1, meio + 1, dir, pos_array, novo_valor);
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    int query(int node, int esq, int dir, int sq, int dq) {
        // Intervalo totalmente ignorado
        if (sq > dir || dq < esq) return 0;
        
        // Intervalo encapsulado perfeitamente
        if (esq >= sq && dir <= dq) return tree[node];
        
        int meio = esq + (dir - esq) / 2;
        int sum_esquerda = query(2 * node, esq, meio, sq, dq);
        int sum_direita = query(2 * node + 1, meio + 1, dir, sq, dq);
        return sum_esquerda + sum_direita;
    }

public:
    SegTree(const vector<int>& arr) {
        n = arr.size();
        // O Tamanho da árvore estática sempre bate em, no maximo, 4*N pra cobrir as extremidades desbalanceadas!
        tree.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    } // Nota: Na árvore as contagens comecam em "Nó = 1", pq 2*0 == 0!

    void update(int pos, int valor) {
        update(1, 0, n - 1, pos, valor);
    }

    int query(int sq, int dq) {
        return query(1, 0, n - 1, sq, dq);
    }
};

void executando_testes() {
    vector<int> patrimonio = {10, 20, 30, 40};
    SegTree st(patrimonio);
    
    // Soma Inicial do Indice 1 (20) ate o 3 (40) = 90
    assert(st.query(1, 3) == 90);
    
    // O Prefeito mudou! Caiu o valor da Cidade Indice 1 (de 20, para ZERAR)!
    st.update(1, 0);
    
    // Agora, Indice 0 ao 3 inteiros era 100, deve ser 80 (! 10 + 0 + 30 + 40!)
    assert(st.query(0, 3) == 80);
    
    cout << "[✅] Testes da SegTree C++ passados. Updates em Tempo real O(logN) estao corretos.\n";
}

int main() {
    executando_testes();
    return 0;
}

Problema Clássico

Problema: Produto do Intervalo Link: Beecrowd 1301

Solução Exata: Como o produto explode (overflow gigante), nós guardamos apenas o mapeamento polar/sinal (+1, -1, 0) em cada folha na SegTree enxuta. * Update: Altera a folha com a divisão do número if(X>0) = 1 e recalcula caminho até raiz. * Query: Traz o Node.Esq * Node.Dir. No fim, imprime + ou -.

Variações e Exercícios

  1. [Soma de Inversões / Fenwick]
    • Foco: Fenwick Tree (Binary Indexed Tree) é absurdamente mais curta que a SegTree (são quase 4 linhas) focada apenas para somas de prefixo lineares. Usada para contar inversões velozes num array.
    • Melhor Link: Beecrowd 1112 (Soma em Área 2D com BIT).
  2. [Horrible Queries]
    • Foco: SegTree com Lazy Propagation (Propagação Preguiçosa). Quando é preciso adicionar + 5 a TUDO entre o índice \([L, R]\) (Range Update massivo), não podemos atualizar folha por folha, senão morremos num brutal \(\mathcal{O}(N)\). “Preguiçosamente” penduramos o número +5 nos nós tetos e não descemos até o cliente exigir!
    • Link: O clássico mundial encontra-se na plataforma Spoj (Spoj HORRIBLE).
Back to top