Árvores de Segmentos (Segment Tree)

1. O Problema das Range Queries

Imagine um vetor gigante com \(10^5\) elementos. Precisamos realizar dois tipos de operações milhares de vezes: 1. Update: Alterar o valor de uma posição específica. 2. Range Query: Calcular a soma (ou mínimo, ou máximo) em um intervalo \([L, R]\).

Estrutura Update Range Query
Vetor Simples \(O(1)\) \(O(N)\) (Lento)
Vetor de Soma Prefixada \(O(N)\) (Recalcular tudo) \(O(1)\)
Segment Tree \(O(\log N)\) \(O(\log N)\)

A Segment Tree é a estrutura definitiva para lidar com intervalos dinâmicos.

2. Estrutura da SegTree

É uma Árvore Binária onde cada nó representa um intervalo. - A Raiz cobre todo o vetor \([0, N-1]\). - Se um nó cobre \([L, R]\), seus filhos cobrem: - Esquerda: \([L, Mid]\) - Direita: \([Mid+1, R]\) - As Folhas representam intervalos unitários \([i, i]\) (os elementos originais).

Representação em Vetor (Heap-like)

Geralmente usamos um vetor de tamanho \(4 \times N\) para armazenar a árvore (para garantir espaço suficiente).

3. Implementação em Java (Range Sum Query)

public class SegmentTree {
    int[] tree; // Armazena as somas
    int[] arr;  // Vetor original
    int n;

    public SegmentTree(int[] arr) {
        this.arr = arr;
        this.n = arr.length;
        tree = new int[4 * n];
        build(1, 0, n - 1);
    }

    // Função Build: O(N)
    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start]; // Folha
        } else {
            int mid = (start + end) / 2;
            build(2 * node, start, mid);       // Constrói filho esquerdo
            build(2 * node + 1, mid + 1, end); // Constrói filho direito
            
            // A soma do nó é a soma dos filhos
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    // Função Update: O(log N)
    public void update(int idx, int val) {
        updateRec(1, 0, n - 1, idx, val);
    }

    private void updateRec(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val; // Atualiza folha
            arr[idx] = val;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                updateRec(2 * node, start, mid, idx, val);
            } else {
                updateRec(2 * node + 1, mid + 1, end, idx, val);
            }
            // Recalcula soma na volta da recursão
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    // Função Query: O(log N)
    public int query(int l, int r) {
        return queryRec(1, 0, n - 1, l, r);
    }

    private int queryRec(int node, int start, int end, int l, int r) {
        // 1. Intervalo totalmente fora
        if (r < start || end < l) {
            return 0; // Elemento neutro da soma
        }

        // 2. Intervalo totalmente dentro
        if (l <= start && end <= r) {
            return tree[node];
        }

        // 3. Parcialmente dentro: divide e conquista
        int mid = (start + end) / 2;
        int p1 = queryRec(2 * node, start, mid, l, r);
        int p2 = queryRec(2 * node + 1, mid + 1, end, l, r);
        
        return p1 + p2;
    }
}

4. Lazy Propagation (Atraso de Atualização)

E se quisermos atualizar um intervalo inteiro update(L, R, +5) (somar 5 em todos de L a R)? Fazer \(N\) updates pontuais custaria \(O(N \log N)\), o que é lento. A técnica Lazy Propagation adia a atualização dos filhos até que eles precisem ser visitados. - Cria-se um vetor lazy[]. - Ao atualizar um nó, marcamos no lazy que seus filhos “devem” algo. - Ao visitar um nó (em query ou update), verificamos se ele tem “dívida” (lazy), aplicamos, e empurramos a dívida para os filhos (Push Down). - Complexidade: mantém \(O(\log N)\) para Update em Faixa.

5. Fenwick Tree (Binary Indexed Tree)

Uma alternativa elegante e compacta à Segment Tree para operações de Soma de Prefixo. - Usa manipulação de bits (index & -index extrai o bit menos significativo - LSB). - Muito mais curta de implementar (cerca de 10 linhas).

Implementação Java

public class BIT {
    int[] tree;
    int n;

    public BIT(int size) {
        this.n = size;
        this.tree = new int[n + 1]; // Indexado em 1
    }

    // Adiciona valor ao índice i: O(log N)
    public void add(int i, int delta) {
        i++; // Ajuste para base-1
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i); // Sobe na árvore
        }
    }

    // Soma de 0 até i: O(log N)
    public int query(int i) {
        i++;
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i); // Desce na árvore
        }
        return sum;
    }
    
    // SomaRange(L, R) = Soma(R) - Soma(L-1)
    public int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

Quando usar qual?

  • BIT: Para problemas de Soma ou contagem de Inversões. Código curto, constante pequena.
  • SegTree: Quando a operação é complexa (Máximo, Mínimo com contagem, MDC) ou requer Lazy Propagation.
Back to top