Fenwick Tree (BIT)

¿Qué es un Fenwick Tree?

Analogía: Imagina que tienes un libro de cuentas donde registras ingresos diarios. Necesitas frecuentemente saber: "¿Cuánto gané del día 5 al día 20?". Un Fenwick Tree organiza las sumas de forma inteligente para que tanto consultar como actualizar sea rápido.

También llamado Binary Indexed Tree (BIT), es una estructura que permite:

• Actualizar un elemento en $O(\log n)$
• Consultar sumas de prefijos en $O(\log n)$

Es más simple y rápido que un Segment Tree, pero solo sirve para operaciones invertibles (como suma).

La idea detrás del BIT

Cada posición i almacena la suma de un rango cuya longitud es el bit menos significativo de i.

i = 1  (001) → almacena v[1]          (1 elemento)
i = 2  (010) → almacena v[1] + v[2]   (2 elementos)
i = 3  (011) → almacena v[3]          (1 elemento)
i = 4  (100) → almacena v[1..4]       (4 elementos)
i = 5  (101) → almacena v[5]          (1 elemento)
i = 6  (110) → almacena v[5] + v[6]   (2 elementos)
i = 7  (111) → almacena v[7]          (1 elemento)
i = 8 (1000) → almacena v[1..8]       (8 elementos)

Implementación

const int MAXN = 200005;
long long bit[MAXN];
int n;

// Sumar val a la posición i
void update(int i, long long val) {
    for (; i <= n; i += i & (-i))  // i & (-i) = bit menos significativo
        bit[i] += val;
}

// Suma de prefijo [1, i]
long long query(int i) {
    long long suma = 0;
    for (; i > 0; i -= i & (-i))
        suma += bit[i];
    return suma;
}

// Suma del rango [l, r]
long long query(int l, int r) {
    return query(r) - query(l - 1);
}

¿Cómo funciona update?

Cuando actualizas la posición i, necesitas actualizar todos los rangos que contienen a i. Subes por el árbol sumando el bit menos significativo:

update(3):  3 → 4 → 8 → 16 → ...
  3 = 011   +1 → 100 = 4
  4 = 100   +4 → 1000 = 8
  8 = 1000  +8 → 10000 = 16

¿Cómo funciona query?

Para obtener la suma [1, i], sumas los bloques correspondientes restando el bit menos significativo:

query(7):  7 → 6 → 4 → 0
  7 = 111  bit[7] = v[7]
  6 = 110  bit[6] = v[5]+v[6]
  4 = 100  bit[4] = v[1]+v[2]+v[3]+v[4]
  Total = v[1..7] ✓

Ejemplo completo

#include <iostream>
using namespace std;

const int MAXN = 200005;
long long bit[MAXN];
int n, q;

void update(int i, long long val) {
    for (; i <= n; i += i & (-i))
        bit[i] += val;
}

long long query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & (-i))
        s += bit[i];
    return s;
}

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

int main() {
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        update(i, x);  // Construir sumando uno por uno
    }

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << "\n";
        } else {
            int pos;
            long long val;
            cin >> pos >> val;
            // Para "cambiar" a val, sumamos la diferencia
            long long actual = query(pos, pos);
            update(pos, val - actual);
        }
    }

    return 0;
}

Contar inversiones con BIT

Una inversión es un par $(i, j)$ donde $i \lt j$ pero $v[i] \gt v[j]$.

Idea: Procesamos de derecha a izquierda. Para cada elemento, contamos cuántos menores ya vimos (están a su derecha).

long long countInversions(vector<int> &v) {
    int n = v.size();
    // Coordenadas comprimidas si los valores son grandes

    long long inversiones = 0;
    memset(bit, 0, sizeof(bit));

    for (int i = n - 1; i >= 0; i--) {
        inversiones += query(v[i] - 1);  // Cuántos menores a mi derecha
        update(v[i], 1);                  // Marcar mi valor
    }

    return inversiones;
}

BIT vs Segment Tree

Regla: Si solo necesitas sumas, usa BIT. Para mínimo/máximo o lazy, usa Segment Tree.

Ejercicio

Dado un arreglo, responde consultas de tipo: ¿cuántos elementos en [l, r] son menores o iguales a K?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 200005;
long long bit[MAXN];
int n, q;

void update(int i, long long val) {
    for (; i <= n; i += i & (-i)) bit[i] += val;
}

long long query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}

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

int main() {
    cin >> n >> q;

    vector<pair<int,int>> vals(n);  // (valor, posición)
    for (int i = 0; i < n; i++) {
        cin >> vals[i].first;
        vals[i].second = i + 1;
    }
    sort(vals.begin(), vals.end());

    struct Query { int l, r, k, idx; };
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].k;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end(),
         [](auto &a, auto &b) { return a.k < b.k; });

    vector<long long> ans(q);
    int j = 0;

    for (auto &qr : queries) {
        while (j < n && vals[j].first <= qr.k) {
            update(vals[j].second, 1);
            j++;
        }
        ans[qr.idx] = query(qr.l, qr.r);
    }

    for (int i = 0; i < q; i++) cout << ans[i] << "\n";

    return 0;
}