🧱 Fenwick (BIT)
Estructura de datos · Se implementa a mano · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 20 de la Ruta de Aprendizaje.
El problema: las sumas siguen llegando, pero los valores cambian
En Sumas de prefijos consultamos a = [3, 1, 4, 2, 5, 0, 2, 1].
Ahora se intercalan preguntas y cambios: por ejemplo, sumar 3 en la posición 4.
Actualizar todos los prefijos afectados puede costar O(n) por cambio.
Fenwick guarda sumas de bloques de distintos tamaños. Una consulta combina unos pocos bloques; una actualización modifica solo los bloques que contienen esa posición. Ambas operaciones cuestan O(log n).
Qué significa cada casilla
En la interfaz del código las posiciones van de 0 a n − 1. Por dentro,
el árbol t usa índices de 1 a n: su índice i corresponde al elemento
original i − 1. En esta sección, los intervalos de los bloques son internos.
t[i] resume el intervalo [i − lowbit(i) + 1, i], donde
lowbit(i) = i & -i es la mayor potencia de dos que divide a i.
Por ejemplo, 6 es 110 en binario: su último 1 representa 2, así que
t[6] guarda dos elementos, los internos 5 y 6.
| Casilla | Bloque interno | Valor inicial |
|---|---|---|
| t[1] | [1,1] | 3 |
| t[2] | [1,2] | 4 |
| t[3] | [3,3] | 4 |
| t[4] | [1,4] | 10 |
| t[5] | [5,5] | 5 |
| t[6] | [5,6] | 5 |
| t[7] | [7,7] | 2 |
| t[8] | [1,8] | 18 |
Una consulta y una actualización sobre esos bloques
Si el diagrama no cabe, deslízalo horizontalmente.
Para sumar hasta la posición externa 6, entramos con índice interno 7:
- Tomamos
t[7] = 2, bloque [7,7], y restamoslowbit(7) = 1. - Tomamos
t[6] = 5, bloque [5,6], y restamoslowbit(6) = 2. - Tomamos
t[4] = 10, bloque [1,4], y restamoslowbit(4) = 4.
Llegamos a cero. Los bloques son contiguos y no se superponen: suman 2 + 5 + 10 = 17, exactamente el prefijo buscado. Para consultar [2,6], restamos el prefijo hasta 1, que vale 4: el resultado es 13.
Ahora sumamos 3 en la posición externa 4, interna 5.
El recorrido de actualización suma el bit bajo: 5 → 6 → 8 → 16.
Nos detenemos antes de 16 porque n = 8. Cambian t[5]: 5→8,
t[6]: 5→8 y t[8]: 18→21. La consulta [2,6] ahora devuelve 16.
Por qué los saltos bastan
En la consulta, restar el bit bajo elimina el último 1 del índice. El bloque que tomamos termina en i y el siguiente termina justo antes de donde empieza ese bloque: no repetimos ni omitimos elementos. Hay como máximo O(log n) bits.
En la actualización necesitamos todos los bloques que contienen la casilla.
El salto i + lowbit(i) lleva al siguiente bloque contenedor: conserva la
posición actual dentro del intervalo y aumenta la potencia de dos de su tamaño.
Repetirlo visita los contenedores hasta salir del arreglo, en O(log n) pasos.
Implementación y uso
struct Fenwick {
int n; vector<long long> t;
Fenwick(int n) : n(n), t(n + 1, 0) {}
void add(int i, long long v) { // i en [0, n)
for (++i; i <= n; i += i & -i) t[i] += v;
}
long long sum(int i) { // suma de [0, i]
long long s = 0;
for (++i; i > 0; i -= i & -i) s += t[i];
return s;
}
long long sum(int l, int r) { return sum(r) - (l ? sum(l - 1) : 0); }
};Construye Fenwick f(8) y carga el arreglo llamando f.add(i, a[i]) para cada
posición. f.sum(2, 6) devuelve 13; después de f.add(4, 3) devuelve 16.
add incrementa; no asigna. Para cambiar 5 por 8 hay que añadir 3,
no 8. Si necesitas asignaciones, conserva el valor anterior para calcular
nuevo - anterior.
| Operación de esta implementación | Tiempo |
|---|---|
| Inicializar las n + 1 casillas en cero | O(n) |
Cargar n valores mediante add | O(n log n) |
| Incrementar una posición | O(log n) |
| Consultar un prefijo o intervalo | O(log n) |
| Memoria | O(n) |
Existe una construcción O(n) propagando bloques, pero no es la utilizada aquí.
Límites y elección de estructura
Las consultas de intervalo requieren 0 <= l <= r < n; add requiere
0 <= i < n. No pases −1 a add: el incremento inicial lo deja en cero,
cuyo bit bajo también es cero, y el ciclo no avanza. sum(-1), en cambio,
devuelve cero y representa el prefijo vacío.
Usa long long si las sumas lo necesitan. Los valores negativos son válidos
para estas operaciones de suma. El módulo 20 - Fenwick y segment tree
presenta otra interfaz, con posiciones desde 1: los bloques son los mismos,
pero debes adaptar las llamadas, no copiar los índices sin mirar.
Fenwick es una buena elección para sumas o conteos con cambios puntuales. Si el arreglo no cambia, Sumas de prefijos responde más rápido. Si necesitas mínimos con modificaciones arbitrarias, esta resta de prefijos no sirve: continúa en Segment tree.
?
La posición externa 4 es la interna 5.
t[4]cubre las internas [1,4], equivalentes a las externas [0,3]. El elemento modificado está fuera de ese bloque. Distinguir ambas numeraciones evita el aparente conflicto.