🧱 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.

CasillaBloque internoValor 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

Índices internos: 1 a 83112432455062718Consulta hasta 7: bloques disjuntost[4] = 10t[6] = 5t[7]Actualizar 5: bloques que lo contienent[5]t[6]t[8]

Si el diagrama no cabe, deslízalo horizontalmente.

Para sumar hasta la posición externa 6, entramos con índice interno 7:

  1. Tomamos t[7] = 2, bloque [7,7], y restamos lowbit(7) = 1.
  2. Tomamos t[6] = 5, bloque [5,6], y restamos lowbit(6) = 2.
  3. Tomamos t[4] = 10, bloque [1,4], y restamos lowbit(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ónTiempo
Inicializar las n + 1 casillas en ceroO(n)
Cargar n valores mediante addO(n log n)
Incrementar una posiciónO(log n)
Consultar un prefijo o intervaloO(log n)
MemoriaO(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.