Estruturas: Árvores Segmentadas / Fenwick

Introdução Teórica

Quando precisamos realizar muitas consultas em intervalos de um vetor (ex: soma de \(L\) a \(R\)) e, ao mesmo tempo, atualizar valores desse vetor, as abordagens ingênuas falham. * Vetor simples: Update \(O(1)\), Query \(O(N)\). * Somas de Prefixo: Update \(O(N)\), Query \(O(1)\). * Árvore Segmentada (SegTree): Update \(O(\log N)\), Query \(O(\log N)\).

Estrutura

A SegTree é uma árvore binária onde cada nó representa um intervalo. A raiz representa \([1, N]\). Os filhos dividem o intervalo ao meio. * As folhas guardam os valores do vetor original. * Nós internos guardam a combinação (soma, min, max, gcd) dos filhos.

Problema Clássico

Problema: Produto do Intervalo Link: Beecrowd 1301

Descrição: Dado um vetor, realizar atualizações de alterar valor e consultas de “qual o sinal (+, -, 0) do produto dos números no intervalo \([L, R]\)”.

Solução: Como o produto explode (overflow), guardamos apenas o sinal (+1, -1, 0) na SegTree. * Cada nó guarda o produto dos sinais dos filhos. * Update: Altera folha e recalcula caminho até raiz. * Query: Combina nós que cobrem o intervalo \([L, R]\).

Variações e Exercícios

1. [Soma de Inversões / Fenwick]
   • Foco: Fenwick Tree (Binary Indexed Tree) é mais fácil de codar para somas de prefixo. Usada para contar inversões num array.
   • Link: [Beecrowd 1558] (Não, procure 1112 Schin -> BIT 2D, ou 2065).
   • Melhor Link: Beecrowd 1112 (Soma em Área 2D com BIT).
2. [Potentiometers]
   • Foco: Problema clássico de soma e update dinâmico.
   • Link: Procurar em UVa 12086. No Beecrowd, o 1301 é o melhor representante introdutório disponível.
3. [Horrible Queries]
   • Foco: Lazy Propagation. Quando é preciso somar um valor em todo um intervalo \([L, R]\) (Range Update), não podemos atualizar folha por folha. “Preguiçosamente” marcamos nós, adiando o trabalho.
   • Link: SPOJ HORRIBLE (Referência clássica).