Árboles de Fenwick (binary indexed)

Qué cubre este capítulo

El segment tree resolvió el problema de "consulta por rango más actualización" para cualquier agregado, a cambio de un árbol real lleno de nodos. Pero la versión más común de ese problema — sumas de prefijo con actualizaciones puntuales — tiene una solución mucho más ligera. El árbol de Fenwick, o binary indexed tree, logra la misma consulta y actualización en O(log n) usando nada más que un array y la representación binaria de los índices: sin nodos, sin apuntadores, con ciclos de dos líneas. Es una de esas estructuras raras que se siente como truco de magia la primera vez que la ves funcionar, y todo su secreto está en que cada índice es responsable de un rango cuya longitud es su bit menos significativo encendido. Este capítulo lo construye, observa los saltos de índice que produce i & -i, y lo muestra ganándole tanto a los baselines con array como al segment tree cuando se trata de sumas.

Un poco de historia

El árbol de Fenwick es joven y tiene un origen preciso: Peter Fenwick lo publicó en 1994, en un artículo titulado "A New Data Structure for Cumulative Frequency Tables." No andaba persiguiendo un problema abstracto — necesitaba frecuencias acumuladas rápidas para codificación aritmética, una técnica de compresión donde tienes que preguntar una y otra vez "¿cuántos símbolos hasta ahora son menores que este?" y actualizar los conteos sobre la marcha. Eso es exactamente suma-de-prefijo-con-actualizaciones. La idea de Fenwick fue que la estructura binaria de los índices ya codifica un árbol, así que no necesitas construir uno: el índice i puede representar implícitamente un rango, y las transiciones entre esos rangos son simplemente sumar o quitar el bit menos significativo encendido. El resultado fue tanto más simple que un segment tree para este caso que se difundió rapidísimo en la programación competitiva, donde "binary indexed tree" o "BIT" ya es vocabulario estándar. Es de esas raras estructuras de datos nombradas por su inventor que llegaron prácticamente en su forma final.

La intuición

Numera las posiciones del array del 1 al n (los árboles de Fenwick son 1-indexed — eso no es una manía, es estructural). Y aquí viene el truco: el índice i es responsable de guardar la suma de un rango del array que termina en i, y la longitud de ese rango es i & -i, el valor del bit menos significativo encendido de i. El índice 6 es 110 en binario, bit menos significativo 2, así que cubre las 2 posiciones que terminan en 6 (o sea, 5 y 6). El índice 8 es 1000, bit menos significativo 8, así que cubre las 8 posiciones de la 1 a la 8. El índice 3 es 011, bit menos significativo 1, así que cubre solo la posición 3. Lo notable es que estos rangos embaldosan el array a la perfección en cada escala.

Como embaldosan, una suma de prefijo es un recorrido hacia abajo por los índices. Para sumar las posiciones 1 a 6, empieza en 6: suma su rango guardado (posiciones 5–6), luego salta a 6 − (6 & -6) = 4, que cubre las posiciones 1–4; súmalo; salta a 4 − 4 = 0 y detente. Dos nodos, y sus rangos 5–6 y 1–4 embaldosan exactamente el 1–6. Una actualización es el espejo — un recorrido hacia arriba. Para sumarle algo a la posición 3, tienes que corregir cada rango guardado que incluya la posición 3: el índice 3 (cubre el 3), luego 3 + (3 & -3) = 4 (cubre 1–4), luego 4 + 4 = 8 (cubre 1–8), luego 8 + 8 = 16, que ya se pasó del final, alto. Cada salto quita o agrega el bit menos significativo encendido, y como un número tiene cuando mucho log n bits, cada recorrido es O(log n). Nunca se construye un árbol; el árbol vive en la aritmética.

Complejidad: cómo escala

El build es $O(n)$, la consulta de prefijo y la actualización puntual son ambas $O(\log n)$ — un salto por cada bit del índice. Una suma de rango son dos sumas de prefijo restadas, sigue siendo $O(\log n)$, y esa resta es justamente la razón por la que el árbol de Fenwick necesita una operación invertible: para obtener la suma de [lo, hi] como prefix(hi) − prefix(lo−1), tienes que poder "restar" la parte que no quieres, lo cual funciona para sumas pero no para min o max. El espacio es $O(n)$ — un solo array, sin overhead por nodo. La gráfica corre la misma carga mixta de consultas y actualizaciones que el capítulo del segment tree:

Con 40000 elementos el árbol de Fenwick corrió la carga mixta en unos 6 ms, contra los 278 ms del array crudo (46× más lento) y los 2433 ms de las sumas de prefijo (403× más lento) — la misma historia de O(log n)-le-gana-a-O(n) que con el segment tree. Pero compáralo con el segment tree mismo: el de aquel capítulo tardó 25 ms en la carga equivalente, así que el árbol de Fenwick es como cuatro veces más rápido para sumas, con una fracción mínima del código y la mitad de la memoria. Ese es el premio de una estructura especializada en exactamente un trabajo.

En qué es bueno y en qué no

El árbol de Fenwick es la herramienta correcta en el instante en que tu problema son sumas de prefijo (o de rango) con actualizaciones puntuales. Es diminuto — un par de ciclos y un array — así que es rápido, cache-friendly, y casi imposible de equivocar una vez que conoces el idioma i & -i. Para frecuencias acumuladas, totales corridos sobre datos mutables, conteo de inversiones y los incontables problemas de "suma de rango con actualizaciones" de la programación competitiva, es la opción por default: le gana al segment tree en factores constantes y les gana a los enfoques con array en complejidad.

Sus límites vienen de esa misma especialización. Solo maneja agregados invertibles — sumas, xors, productos (si son distintos de cero) — porque las consultas por rango restan prefijos; para min, max o gcd, donde no puedes restar, necesitas un segment tree. Responde de manera natural a consultas ancladas al prefijo; las consultas estructurales arbitrarias piden los rangos explícitos del segment tree. Y su 1-indexing y su manejo de bits, aunque cortos, son famosamente propensos a error hasta que te hacen clic. El árbol de Fenwick es el especialista: imbatible en su carril angosto, inaplicable fuera de él.

Los datos, o las entradas

El face-off corre 5000 operaciones mixtas de consulta de prefijo y actualización con tamaños crecientes — la misma carga que el capítulo del segment tree, así que las dos estructuras son directamente comparables. La animación traza una consulta de suma de prefijo y una actualización sobre un árbol de ocho elementos, para que puedas ver los saltos de i & -i recorriendo los índices hacia abajo y hacia arriba.

Constrúyelo, una función a la vez

La suma de prefijo recorre hacia abajo, restando el bit menos significativo encendido:

def prefix_sum(self, i, probe=None):
    """Sum of elements 1..i in O(log n). Walk DOWN: add tree[i], then jump to
    i - (i & -i) — removing the lowest set bit — until i reaches 0. Each node covers a
    range of length equal to its lowest set bit, and those ranges tile [1..i] exactly,
    so their stored sums add up to the prefix."""
    total = 0
    while i > 0:
        total += self._tree[i]
        if probe is not None:
            probe.append(i)
        i -= i & -i
    return total

La actualización recorre hacia arriba, sumándolo:

def update(self, i, delta, probe=None):
    """Add `delta` to element i (1-indexed) in O(log n). Walk UP: after touching index
    i, jump to i + (i & -i) — adding the lowest set bit — which is the next node whose
    range covers position i. Each jump clears toward the high bits, so at most log n
    steps reach past the end."""
    while i <= self._n:
        self._tree[i] += delta
        if probe is not None:
            probe.append(i)
        i += i & -i

Y una suma de rango es la diferencia de dos prefijos — el paso que exige un agregado invertible:

def range_sum(self, lo, hi):
    """Sum of [lo..hi] by subtracting prefixes — the trick that needs an INVERTIBLE
    aggregate (why Fenwick trees do sums, not min/max)."""
    return self.prefix_sum(hi) - self.prefix_sum(lo - 1)

Míralo funcionar

Aquí está la aritmética de índices en movimiento sobre ocho posiciones. Primero un prefix_sum(6): el naranja marca el índice actual, el azul los índices ya sumados. Míralo empezar en 6, sumar el rango de ese nodo, y saltar a 4 restando el bit menos significativo encendido (6 − 2 = 4), y luego a 0 — dos nodos cuyos rangos embaldosan del 1 al 6. Después una actualización a la posición 3: recorre en el otro sentido, 3 → 4 → 8, sumando el bit menos significativo encendido cada vez para tocar todos los nodos cuyo rango cubre la posición 3. Los subtítulos muestran el binario de cada índice para que veas directo el salto del bit menos significativo. No se dibuja ningún árbol porque no hay árbol — solo un array y estos saltos:

El código completo

Las dos versiones en un solo lugar — alterna entre ellas. La pestaña "desde cero" es el árbol de Fenwick — fíjate en lo poquito que hay. La pestaña de librería son los dos baselines con array a los que les gana (array crudo y sumas de prefijo), porque no hay árbol de Fenwick en la librería estándar; el punto entero es que esta estructura es lo bastante chica para escribirla de memoria.

"""The Fenwick tree — also called a binary indexed tree, or BIT — the lean specialist for
prefix sums with updates. It does the same O(log n) prefix-query and point-update job as a
segment tree, for the special case of an invertible aggregate like sum, in a fraction of
the code and memory: one array and a two-line loop each way.

Its whole cleverness is in the indices. Node i is "responsible" for a range of the array
whose length is the lowest set bit of i — the value `i & -i`. Those ranges tile the array
perfectly, so a prefix sum walks *down* the indices by repeatedly subtracting the lowest
set bit, and an update walks *up* by adding it. No tree of nodes and pointers — just
arithmetic on the binary representation of the index.
"""


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._tree = [0] * (n + 1)          # 1-indexed; index 0 is unused

    @classmethod
    def from_data(cls, data):
        """O(n) build: copy the values in, then let each index push its running total up
        to the parent that covers it. Faster than n separate updates."""
        ft = cls(len(data))
        ft._tree = [0] + list(data)
        for i in range(1, ft._n + 1):
            j = i + (i & -i)
            if j <= ft._n:
                ft._tree[j] += ft._tree[i]
        return ft

    # region: update
    def update(self, i, delta, probe=None):
        """Add `delta` to element i (1-indexed) in O(log n). Walk UP: after touching index
        i, jump to i + (i & -i) — adding the lowest set bit — which is the next node whose
        range covers position i. Each jump clears toward the high bits, so at most log n
        steps reach past the end."""
        while i <= self._n:
            self._tree[i] += delta
            if probe is not None:
                probe.append(i)
            i += i & -i
    # endregion

    # region: prefix_sum
    def prefix_sum(self, i, probe=None):
        """Sum of elements 1..i in O(log n). Walk DOWN: add tree[i], then jump to
        i - (i & -i) — removing the lowest set bit — until i reaches 0. Each node covers a
        range of length equal to its lowest set bit, and those ranges tile [1..i] exactly,
        so their stored sums add up to the prefix."""
        total = 0
        while i > 0:
            total += self._tree[i]
            if probe is not None:
                probe.append(i)
            i -= i & -i
        return total
    # endregion

    # region: range_sum
    def range_sum(self, lo, hi):
        """Sum of [lo..hi] by subtracting prefixes — the trick that needs an INVERTIBLE
        aggregate (why Fenwick trees do sums, not min/max)."""
        return self.prefix_sum(hi) - self.prefix_sum(lo - 1)
    # endregion

"""No Fenwick tree in the standard library — it's a build-it-yourself structure. The
baselines are the same two array approaches from the segment-tree chapter, each fast at one
operation and O(n) at the other:

  - a RAW array: O(1) update, O(n) prefix query;
  - a PREFIX-SUM array: O(1) query, O(n) update (rebuild).

The Fenwick tree matches a segment tree's O(log n) for BOTH — on sums specifically — with far
less code, which is the point of the face-off.
"""


# region: raw_array
class RawArray:
    """Raw values: update is trivial, prefix sum re-adds the slice — O(n)."""

    def __init__(self, data):
        self._d = list(data)

    def prefix_sum(self, i):
        return sum(self._d[:i])                 # O(n)

    def update(self, i, delta):
        self._d[i] += delta                     # O(1)
# endregion


# region: prefix_sums
class PrefixSums:
    """Precomputed prefix sums: O(1) query, but any update forces an O(n) rebuild."""

    def __init__(self, data):
        self._d = list(data)
        self._rebuild()

    def _rebuild(self):
        self._p = [0]
        for x in self._d:
            self._p.append(self._p[-1] + x)

    def prefix_sum(self, i):
        return self._p[i]                       # O(1)

    def update(self, i, delta):
        self._d[i] += delta
        self._rebuild()                         # O(n)
# endregion

Desde cero vs librería

La comparación contra los baselines con array cuenta la misma historia que el segment tree — O(log n) aplasta a O(n) en una carga mixta, 46× y 403× aquí. Pero el número que define este capítulo es el que tienes que cargar entre dos capítulos: 6 ms del árbol de Fenwick contra 25 ms del segment tree en la carga equivalente. Misma clase asintótica, mismo problema, pero la constante diminuta del árbol de Fenwick — un array, ciclos de dos líneas, sin objetos nodo, cache-friendly — lo hace cuatro veces más rápido en la práctica. Esta es la lección de los factores constantes convertida en principio de diseño: cuando una estructura general y una especializada tienen el mismo Big-O, el especialista casi siempre gana en la constante, así que empata la herramienta con el problema exacto. El segment tree es la respuesta correcta para min/max o actualizaciones por rango; para sumas de prefijo, el árbol de Fenwick es más chico, más rápido y más difícil de equivocar.

Dónde te lo vas a encontrar de verdad

Los árboles de Fenwick corren en donde sea que cambien conteos acumulados. Los codificadores aritméticos y de rango — la aplicación original de Fenwick — los usan para frecuencias adaptativas de símbolos. Las bases de datos y los motores de analítica los usan para agregados corridos sobre datos mutables. Son la herramienta estándar para contar inversiones (qué tan lejos está una secuencia de estar ordenada) y para estadísticas de orden con actualizaciones. Y en programación competitiva son omnipresentes — se recurre al "BIT" por reflejo cada que un problema dice "suma de prefijo" y "actualización" en la misma frase. Cada que necesites un total corrido sobre datos que no dejan de cambiar, el árbol de Fenwick es la estructura más ligera que lo hace en O(log n).

Conclusiones

Un árbol de Fenwick guarda la información de sumas de prefijo de forma implícita en la estructura binaria de sus índices: el índice i cubre las i & -i posiciones que terminan en i, esos rangos embaldosan el array, y las consultas recorren hacia abajo restando el bit menos significativo encendido mientras que las actualizaciones recorren hacia arriba sumándolo — ambas $O(\log n)$, en un array y dos ciclos cortos. Es la alternativa especializada y ligera al segment tree para agregados invertibles, cuatro veces más rápida en la prueba de este capítulo y con la décima parte del código, al costo de solo hacer sumas, no min ni max.

Con esto se completan los árboles de consulta por rango, y casi todo el nivel de árboles. Quedan dos estructuras, y ambas se salen del mundo de los árboles binarios. El siguiente capítulo, el B-tree, es el árbol balanceado reimaginado para disco: en vez de dos hijos por nodo tiene cientos, porque cuando cada nodo es un bloque de disco, minimizar la cantidad de bloques que lees importa más que cualquier otra cosa — y por eso los B-trees, no los árboles rojo-negro, indexan todas las bases de datos y sistemas de archivos del planeta.