Árbol de Fenwick (BIT)

Sea $f$ alguna operación de grupo (una función binaria asociativa sobre un conjunto con elemento identidad y elementos inversos) y $A$ un arreglo de enteros de longitud $N$. Denotamos la notación infija de $f$ como $\ast$∗; es decir, $f(x,y) = x$y para enteros arbitrarios $x,y$. (Como es asociativa, omitiremos los paréntesis para el orden de aplicación de $f$ cuando usemos notación infija.)

El Árbol de Fenwick es una estructura de datos que:

• calcula el valor de la función $f$ en el rango dado $[l, r]$ (es decir, $A_l * A_{l+1} * \dots * A_r$) en tiempo $O(\log N)$
• actualiza el valor de un elemento de $A$ en tiempo $O(\log N)$
• requiere $O(N)$ de memoria (la misma cantidad que requiere $A$)
• es fácil de usar y de programar, especialmente en el caso de arreglos multidimensionales

La aplicación más común de un Árbol de Fenwick es calcular la suma de un rango. Por ejemplo, usando la suma sobre el conjunto de los enteros como operación de grupo, es decir $f(x,y) = x + y$: la operación binaria, $*$, es $+$ en este caso, así que $A_l * A_{l+1} * \dots * A_r = A_l + A_{l+1} + \dots + A_{r}$.

El Árbol de Fenwick también se llama Binary Indexed Tree (BIT). Fue descrito por primera vez en un artículo titulado “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).

Descripción

Visión general

Por simplicidad, asumiremos que la función $f$ está definida como $f(x,y) = x + y$ sobre los enteros.

Supongamos que nos dan un arreglo de enteros, $A[0 \dots N-1]$. (Nótese que usamos indexación desde cero.) Un Árbol de Fenwick es simplemente un arreglo, $T[0 \dots N-1]$, donde cada elemento es igual a la suma de elementos de $A$ en algún rango, $[g(i), i]$:

$$T_i = \sum_{j = g(i)}^{i}{A_j}$$

donde $g$ es alguna función que cumple $0 \le g(i) \le i$. Definiremos $g$ en los próximos párrafos.

La estructura de datos se llama árbol porque existe una representación agradable en forma de árbol, aunque no necesitamos modelar un árbol real con nodos y aristas. Solo necesitamos mantener el arreglo $T$ para atender todas las consultas.

Nota: El Árbol de Fenwick que presentamos aquí usa indexación desde cero. Muchas personas usan una versión del Árbol de Fenwick con indexación desde uno. Por eso, en la sección de implementación también hay una implementación alternativa que usa indexación desde uno. Ambas versiones son equivalentes en complejidad temporal y espacial.

Ahora podemos escribir algo de pseudocódigo para las dos operaciones mencionadas arriba. Abajo, obtenemos la suma de elementos de $A$ en el rango $[0, r]$ y actualizamos (incrementamos) algún elemento $A_i$:

def sum(int r):
    res = 0
    while (r >= 0):
        res += t[r]
        r = g(r) - 1
    return res
 
def increase(int i, int delta):
    for all j with g(j) <= i <= j:
        t[j] += delta

La función sum funciona de la siguiente manera:

1. Primero, añade la suma del rango $[g(r), r]$ (es decir, $T[r]$) al result.
2. Luego, “salta” al rango $[g(g(r)-1), g(r)-1]$ y añade la suma de este rango al result.
3. Esto continúa hasta que “salta” de $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ a $[g(-1), -1]$; ahí es donde la función sum deja de saltar.

La función increase funciona con la misma analogía, pero “salta” en la dirección de índices crecientes:

1. La suma de cada rango de la forma $[g(j), j]$ que cumple la condición $g(j) \le i \le j$ se incrementa en delta; es decir, t[j] += delta. Por lo tanto, actualiza todos los elementos de $T$ que corresponden a rangos en los que está $A_i$.

La complejidad de sum y de increase depende de la función $g$. Hay muchas formas de elegir la función $g$ tal que $0 \le g(i) \le i$ para todo $i$. Por ejemplo, funciona la función $g(i) = i$, que da $T = A$ (en cuyo caso, las consultas de suma son lentas). También podríamos tomar la función $g(i) = 0$. Esto correspondería a arreglos de sumas de prefijos (en cuyo caso, encontrar la suma del rango $[0, i]$ solo toma tiempo constante; sin embargo, las actualizaciones son lentas). La parte ingeniosa del algoritmo de los Árboles de Fenwick es cómo usa una definición especial de la función $g$ que puede manejar ambas operaciones en tiempo $O(\log N)$.

Definición de $g(i)$ { data-toc-label=‘Definición de $g(i)$’ }

El cálculo de $g(i)$ se define usando la siguiente operación simple: reemplazamos todos los bits $1$ finales en la representación binaria de $i$ por bits $0$.

En otras palabras, si el dígito menos significativo de $i$ en binario es $0$, entonces $g(i) = i$. Y en caso contrario el dígito menos significativo es un $1$, y tomamos este $1$ y todos los demás $1$s finales y los invertimos.

Por ejemplo obtenemos

$$\begin{array}{rllll}& {\displaystyle g(11)=g({1011}_2)={1000}_2}& {\displaystyle =8}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(12)=g({1100}_2)={1100}_2}& {\displaystyle =12}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(13)=g({1101}_2)={1100}_2}& {\displaystyle =12}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(14)=g({1110}_2)={1110}_2}& {\displaystyle =14}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(15)=g({1111}_2)={0000}_2}& {\displaystyle =0}& & \\ & {\displaystyle }& & \end{array}$$$$\begin{align} g(11) = g(1011_2) = 1000_2 &= 8 \\ g(12) = g(1100_2) = 1100_2 &= 12 \\ g(13) = g(1101_2) = 1100_2 &= 12 \\ g(14) = g(1110_2) = 1110_2 &= 14 \\ g(15) = g(1111_2) = 0000_2 &= 0 \\ \end{align}$$

Existe una implementación simple usando operaciones de bits para la operación no trivial descrita arriba:

$$g(i) = i & (i+1),$$

donde $&$ es el operador AND bit a bit. No es difícil convencerse de que esta solución hace lo mismo que la operación descrita arriba.

Ahora, solo necesitamos encontrar una forma de iterar sobre todos los $j$ tales que $g(j) \le i \le j$.

Es fácil ver que podemos encontrar todos esos $j$ empezando desde $i$ y activando el último bit no activado. Llamaremos a esta operación $h(j)$. Por ejemplo, para $i = 10$ tenemos:

$$\begin{array}{rllll}& {\displaystyle 10}& {\displaystyle ={0001010}_2}& & \\ & {\displaystyle }& & \\ & {\displaystyle h(10)=11}& {\displaystyle ={0001011}_2}& & \\ & {\displaystyle }& & \\ & {\displaystyle h(11)=15}& {\displaystyle ={0001111}_2}& & \\ & {\displaystyle }& & \\ & {\displaystyle h(15)=31}& {\displaystyle ={0011111}_2}& & \\ & {\displaystyle }& & \\ & {\displaystyle h(31)=63}& {\displaystyle ={0111111}_2}& & \\ & {\displaystyle }& & \\ & {\displaystyle \mathrm{⋮}}& {\displaystyle }& & \end{array}$$$$\begin{align} 10 &= 0001010_2 \\ h(10) = 11 &= 0001011_2 \\ h(11) = 15 &= 0001111_2 \\ h(15) = 31 &= 0011111_2 \\ h(31) = 63 &= 0111111_2 \\ \vdots & \end{align}$$

Como era de esperar, también existe una forma simple de calcular $h$ usando operaciones de bits:

$$h(j) = j | (j+1),$$

donde $|$ es el operador OR bit a bit.

La siguiente imagen muestra una posible interpretación del Árbol de Fenwick como árbol. Los nodos del árbol muestran los rangos que cubren.

Implementación

Suma en un arreglo unidimensional

Aquí presentamos una implementación del Árbol de Fenwick para consultas de suma y actualizaciones de un solo elemento.

El Árbol de Fenwick normal solo puede responder consultas de suma del tipo $[0, r]$ usando sum(int r), pero también podemos responder otras consultas del tipo $[l, r]$ calculando dos sumas $[0, r]$ y $[0, l-1]$ y restándolas. Esto se maneja en el método sum(int l, int r).

Además, esta implementación soporta dos constructores. Se puede crear un Árbol de Fenwick inicializado con ceros, o se puede convertir un arreglo existente a la forma de Fenwick.

struct FenwickTree {
    vector<int> bit;  // Árbol de Fenwick (BIT)
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

Construcción lineal

La implementación de arriba requiere tiempo $O(N \log N)$. Es posible mejorarlo a tiempo $O(N)$.

La idea es que el número $a[i]$ en el índice $i$ contribuirá al rango guardado en $bit[i]$, y a todos los rangos a los que contribuye el índice $i | (i + 1)$. Así, al ir sumando los números en orden, solo hay que empujar la suma actual hacia el siguiente rango, donde después se empujará hacia el siguiente rango, y así sucesivamente.

FenwickTree(vector<int> const &a) : FenwickTree(a.size()){
    for (int i = 0; i < n; i++) {
        bit[i] += a[i];
        int r = i | (i + 1);
        if (r < n) bit[r] += bit[i];
    }
}

Mínimo de $[0, r]$ en un arreglo unidimensional { data-toc-label=‘Mínimo de $[0, r]$ en un arreglo unidimensional’ }

Es evidente que no hay una forma fácil de encontrar el mínimo del rango $[l, r]$ usando un Árbol de Fenwick, ya que el Árbol de Fenwick solo puede responder consultas del tipo $[0, r]$. Además, cada vez que se hace update de un valor, el nuevo valor tiene que ser menor que el valor actual. Ambas limitaciones importantes se deben a que la operación $min$ junto con el conjunto de los enteros no forma un grupo, porque no hay elementos inversos.

struct FenwickTreeMin {
    vector<int> bit;
    int n;
    const int INF = (int)1e9;

    FenwickTreeMin(int n) {
        this->n = n;
        bit.assign(n, INF);
    }

    FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            update(i, a[i]);
    }

    int getmin(int r) {
        int ret = INF;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = min(ret, bit[r]);
        return ret;
    }

    void update(int idx, int val) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] = min(bit[idx], val);
    }
};

Nota: es posible implementar un Árbol de Fenwick que pueda manejar consultas arbitrarias de mínimo en un rango y actualizaciones arbitrarias. El artículo Efficient Range Minimum Queries using Binary Indexed Trees  describe ese enfoque. Sin embargo, con ese enfoque hay que mantener un segundo árbol indexado binario sobre los datos, con una estructura ligeramente distinta, ya que un solo árbol no alcanza para guardar los valores de todos los elementos del arreglo. La implementación también es bastante más difícil comparada con la implementación normal para sumas.

Suma en un arreglo bidimensional

Como se afirmó antes, es muy fácil implementar un Árbol de Fenwick para un arreglo multidimensional.

struct FenwickTree2D {
    vector<vector<int>> bit;
    int n, m;
 
    // init(...) { ... }
 
    int sum(int x, int y) {
        int ret = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
                ret += bit[i][j];
        return ret;
    }
 
    void add(int x, int y, int delta) {
        for (int i = x; i < n; i = i | (i + 1))
            for (int j = y; j < m; j = j | (j + 1))
                bit[i][j] += delta;
    }
};

Enfoque con indexación desde uno

Para este enfoque cambiamos un poco los requisitos y la definición de $T[]$ y $g()$. Queremos que $T[i]$ guarde la suma de $[g(i)+1; i]$. Esto cambia un poco la implementación, y permite una definición igualmente agradable de $g(i)$:

def sum(int r):
    res = 0
    while (r > 0):
        res += t[r]
        r = g(r)
    return res
 
def increase(int i, int delta):
    for all j with g(j) < i <= j:
        t[j] += delta

El cálculo de $g(i)$ se define como: invertir el último bit $1$ activado en la representación binaria de $i$.

$$\begin{array}{rllll}& {\displaystyle g(7)=g({111}_2)={110}_2}& {\displaystyle =6}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(6)=g({110}_2)={100}_2}& {\displaystyle =4}& & \\ & {\displaystyle }& & \\ & {\displaystyle g(4)=g({100}_2)={000}_2}& {\displaystyle =0}& & \\ & {\displaystyle }& & \end{array}$$$$\begin{align} g(7) = g(111_2) = 110_2 &= 6 \\ g(6) = g(110_2) = 100_2 &= 4 \\ g(4) = g(100_2) = 000_2 &= 0 \\ \end{align}$$

El último bit activado se puede extraer usando $i & (-i)$, así que la operación se puede expresar como:

$$g(i) = i - (i & (-i)).$$

Y no es difícil ver que hay que cambiar todos los valores $T[j]$ en la secuencia $i,~ h(i),~ h(h(i)),~ \dots$ cuando se quiere actualizar $A[j]$, donde $h(i)$ se define como:

$$h(i) = i + (i & (-i)).$$

Como se puede ver, la principal ventaja de este enfoque es que las operaciones binarias se complementan de forma muy elegante.

La siguiente implementación se puede usar como las otras implementaciones, pero internamente usa indexación desde uno.

struct FenwickTreeOneBasedIndexing {
    vector<int> bit;  // Árbol de Fenwick (BIT)
    int n;

    FenwickTreeOneBasedIndexing(int n) {
        this->n = n + 1;
        bit.assign(n + 1, 0);
    }

    FenwickTreeOneBasedIndexing(vector<int> a)
        : FenwickTreeOneBasedIndexing(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int idx) {
        int ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] += delta;
    }
};

Operaciones de rango

Un Árbol de Fenwick puede soportar las siguientes operaciones de rango:

1. Actualización puntual y consulta de rango
2. Actualización de rango y consulta puntual
3. Actualización de rango y consulta de rango

1. Actualización puntual y consulta de rango

Esto es simplemente el Árbol de Fenwick ordinario explicado arriba.

2. Actualización de rango y consulta puntual

Con trucos simples también podemos hacer las operaciones inversas: incrementar rangos y consultar valores individuales.

Sea el Árbol de Fenwick inicializado con ceros. Supongamos que queremos incrementar el intervalo $[l, r]$ en $x$. Hacemos dos operaciones de actualización puntual sobre el Árbol de Fenwick: add(l, x) y add(r+1, -x).

Si queremos obtener el valor de $A[i]$, solo necesitamos tomar la suma de prefijos usando el método ordinario de suma de rango. Para ver por qué esto es cierto, podemos enfocarnos de nuevo en la operación de incremento anterior. Si $i < l$, entonces las dos operaciones de actualización no tienen efecto sobre la consulta y obtenemos la suma $0$. Si $i \in [l, r]$, entonces obtenemos la respuesta $x$ por la primera operación de actualización. Y si $i > r$, entonces la segunda operación de actualización cancelará el efecto de la primera.

La siguiente implementación usa indexación desde uno.

void add(int idx, int val) {
    for (++idx; idx < n; idx += idx & -idx)
        bit[idx] += val;
}
 
void range_add(int l, int r, int val) {
    add(l, val);
    add(r + 1, -val);
}
 
int point_query(int idx) {
    int ret = 0;
    for (++idx; idx > 0; idx -= idx & -idx)
        ret += bit[idx];
    return ret;
}

Nota: por supuesto también es posible incrementar un solo punto $A[i]$ con range_add(i, i, val).

3. Actualización de rango y consulta de rango

Para soportar tanto actualizaciones de rango como consultas de rango usaremos dos BIT, a saber $B_1[]$ y $B_2[]$, inicializados con ceros.

Supongamos que queremos incrementar el intervalo $[l, r]$ en el valor $x$. De forma similar al método anterior, hacemos dos actualizaciones puntuales sobre $B_1$: add(B1, l, x) y add(B1, r+1, -x). Y también actualizamos $B_2$. Los detalles se explican más adelante.

def range_add(l, r, x):
    add(B1, l, x)
    add(B1, r+1, -x)
    add(B2, l, x*(l-1))
    add(B2, r+1, -x*r))

Después de la actualización de rango $(l, r, x)$ la consulta de suma de rango debería devolver los siguientes valores:

$$sum[0, i]=$$$$\begin{cases} 0 &amp; i &lt; l \\ x \cdot (i-(l-1)) &amp; l \le i \le r \\ x \cdot (r-l+1) &amp; i &gt; r \\ \end{cases}$$

Podemos escribir la suma de rango como diferencia de dos términos, donde usamos $B_1$ para el primer término y $B_2$ para el segundo. La diferencia de las consultas nos dará la suma de prefijos sobre $[0, i]$.

$$\begin{array}{rllll}& {\displaystyle sum[0,i]}& {\displaystyle =sum(B_1,i)\cdot i-sum(B_2,i)}& & \\ & {\displaystyle }& & \\ & {\displaystyle }& {\displaystyle =\{\begin{array}{ll}0\cdot i-0& i<l\\ \\ x\cdot i-x\cdot (l-1)& l\le i\le r\\ \\ 0\cdot i-(x\cdot (l-1)-x\cdot r)& i>r\\ \end{array}}& & \end{array}$$$$\begin{align} sum[0, i] &amp;= sum(B_1, i) \cdot i - sum(B_2, i) \\ &amp;= \begin{cases} 0 \cdot i - 0 &amp; i &lt; l\\ x \cdot i - x \cdot (l-1) &amp; l \le i \le r \\ 0 \cdot i - (x \cdot (l-1) - x \cdot r) &amp; i &gt; r \\ \end{cases} \end{align}$$

La última expresión es exactamente igual a los términos requeridos. Así podemos usar $B_2$ para eliminar los términos extra cuando multiplicamos $B_1[i]\times i$.

Podemos encontrar sumas de rangos arbitrarios calculando las sumas de prefijos para $l-1$ y $r$ y tomando de nuevo su diferencia.

def add(b, idx, x):
    while idx <= N:
        b[idx] += x
        idx += idx & -idx
 
def range_add(l,r,x):
    add(B1, l, x)
    add(B1, r+1, -x)
    add(B2, l, x*(l-1))
    add(B2, r+1, -x*r)
 
def sum(b, idx):
    total = 0
    while idx > 0:
        total += b[idx]
        idx -= idx & -idx
    return total
 
def prefix_sum(idx):
    return sum(B1, idx)*idx -  sum(B2, idx)
 
def range_sum(l, r):
    return prefix_sum(r) - prefix_sum(l-1)

Problemas de práctica

• UVA 12086 - Potentiometers 
• LOJ 1112 - Curious Robin Hood 
• LOJ 1266 - Points in Rectangle 
• Codechef - SPREAD 
• SPOJ - CTRICK 
• SPOJ - MATSUM 
• SPOJ - DQUERY 
• SPOJ - NKTEAM 
• SPOJ - YODANESS 
• SRM 310 - FloatingMedian 
• SPOJ - Ada and Behives 
• Hackerearth - Counting in Byteland 
• DevSkill - Shan and String (archived) 
• Codeforces - Little Artem and Time Machine 
• Codeforces - Hanoi Factory 
• SPOJ - Tulip and Numbers 
• SPOJ - SUMSUM 
• SPOJ - Sabir and Gifts 
• SPOJ - The Permutation Game Again 
• SPOJ - Zig when you Zag 
• SPOJ - Cryon 
• SPOJ - Weird Points 
• SPOJ - Its a Murder 
• SPOJ - Bored of Suffixes and Prefixes 
• SPOJ - Mega Inversions 
• Codeforces - Subsequences 
• Codeforces - Ball 
• GYM - The Kamphaeng Phet’s Chedis 
• Codeforces - Garlands 
• Codeforces - Inversions after Shuffle 
• GYM - Cairo Market 
• Codeforces - Goodbye Souvenir 
• SPOJ - Ada and Species 
• Codeforces - Thor 
• CSES - Forest Queries II 
• Latin American Regionals 2017 - Fundraising 

Otras fuentes

• Fenwick tree on Wikipedia 
• Binary indexed trees tutorial on TopCoder 
• Range updates and queries