Fenwick Tree (o Binary Indexed Tree, BIT) es una estructura compacta para prefix sums y point updates en O(log n). Es más simple y rápida que segment tree para operaciones de suma.

La magia está en usar el bit menos significativo (LSB) para saltar entre nodos relevantes.

Estructura

Array 1-based bit[1..n] donde bit[i] almacena la suma de un rango específico.

LSB: i & -i da el bit menos significativo de i.

• i += (i & -i): salta al siguiente nodo que cubre el rango actual (para update).
• i -= (i & -i): salta al nodo padre (para query).

Point Update

add(i, delta):

• Mientras i <= n: bit[i] += delta, luego i += (i & -i).

Prefix Query

sum(i):

• Inicializa res = 0.
• Mientras i > 0: res += bit[i], luego i -= (i & -i).

Range Query

range_sum(l, r) = sum(r) - sum(l-1).

Ejemplo

Array: [1, 3, 5, 7, 9], n = 5.

Construye BIT con updates:

• add(1,1): actualiza bit[1], bit[2], bit[4].
• add(2,3): actualiza bit[2], bit[4].
• add(3,5): actualiza bit[3], bit[4].
• add(4,7): actualiza bit[4].
• add(5,9): actualiza bit[5].

sum(3) = bit[3] + bit[2] = 5 + 4 = 9 = 1 + 3 + 5.

Comparación

Limitaciones

• No soporta range update nativamente — requiere técnica de “two BITs” o conversión a point updates.
• Solo operaciones asociativas — suma, xor, gcd; no min/max con updates arbitrarias.
• 1-based — requiere conversión desde 0-based arrays.

Aplicaciones

• Dinamic programming — prefix sums con updates
• Inversion count — BIT sobre valores comprimidos
• Range queries — cuando solo necesitas suma
• Enseñanza — introduce LSB y trees compactas

Trayectoria de Práctica

1. Implementa Fenwick tree; traza add y sum.
2. Implementa range sum: range_sum(l,r) = sum(r) - sum(l-1).
3. Investiga build O(n): ¿cómo construye desde array en tiempo lineal?
4. Investiga two BITs para range update + range query.
5. Compara con segment tree: ¿cuándo elegir cada uno?