Vamos começar com algumas questões fundamentais sobre essa estrutura de dados.

O que é uma Árvore Binária Indexada?

Como o nome sugere, utiliza-se um vetor para representar uma estrutura hierárquica. Uma dúvida comum é: por que não construir uma árvore diretamente? A resposta é que, para os problemas que a Árvore Binária Indexada (Fenwick Tree) resolve, a construção de uma árvore completa é desnecessária. Essa abordagem é conceitualmente similar à construção de uma Trie.

Quais problemas ela resolve?

Esta estrutura é eficiente para resolver a grande maioria dos problemas que envolvem atualizações e consultas de soma em intervalos.

Diferenças entre Árvore Binária Indexada e Segment Tree

Todo problema resolvido por uma Fenwick Tree pode ser resolvido por uma Segment Tree. A principal diferença está na eficiência: a Fenwick Tree possui um fator constante muito menor em suas operações. É como usar uma string para simular números grandes: funciona, mas para uma simples adição de 1+1, seria um exagero.

Vantagens e Desvantagens

• Vantagens: A complexidade tanto para atualização quanto para consulta é O(log N). Comparada à Segment Tree, o fator constante é significativamente menor, sendo mais rápida e mais simples de implementar.
• Desvantagens: Para problemas de intervalo mais complexos, como encontrar o mínimo em um intervalo, a estrutura não é adequada.

Entendendo o LOWBIT

Vamos analisar a imagem abaixo para entender a estrutura.

Observando a figura, podemos deduzir que:

• C[1] = A[1]
• C[2] = A[1] + A[2]
• C[3] = A[3]
• C[4] = A[1] + A[2] + A[3] + A[4]
• C[5] = A[5]
• C[6] = A[5] + A[6]
• C[7] = A[7]
• C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

A estrutura segue um padrão claro: C[i] = A[i - 2^k + 1] + A[i - 2^k + 2] + ... + A[i], onde k é o número de zeros à direita na representação binária de i.

Como encontrar o valor de 2^k? A operação chave é: i & (-i). Isso isola o bit menos significativo (LSB) de i.

Exemplo: Para i = 7 (binário 00000111), seu complemento de dois é 11111001. Realizando a operação AND entre 00000111 e 11111001, obtemos 00000001, que é 1.

Implementação do lowbit:

inline int lowbit(int x) {
    return x & (-x);
}

Fenwick Tree Unidimensional

1. Atualização de Ponto e Consulta de Intervalo

Atualização de ponto:

inline void update(int pos, int val) {
    while (pos <= n) {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}

Consulta de intervalo: Para obter a soma entre x e y, calculamos a soma de 1 a y e subtraímos a soma de 1 a (x-1).

inline int query(int pos) {
    int sum = 0;
    while (pos > 0) {
        sum += tree[pos];
        pos -= lowbit(pos);
    }
    return sum;
}

Portanto, para uma consulta no intervalo [x, y], usamos query(y) - query(x - 1).

Código de exemplo:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 5;
int n, q, arr[MAXN], tree[MAXN];

inline int lowbit(int x) { return x & (-x); }
inline void update(int pos, int val) {
    while (pos <= n) {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}
inline int query(int pos) {
    int res = 0;
    while (pos > 0) {
        res += tree[pos];
        pos -= lowbit(pos);
    }
    return res;
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        update(i, arr[i]);
    }
    while (q--) {
        int op, a, b, c;
        cin >> op;
        if (op == 1) {
            cin >> a >> b;
            update(a, b);
        } else {
            cin >> a >> b;
            cout << query(b) - query(a - 1) << endl;
        }
    }
    return 0;
}

2. Atualização de Intervalo e Consulta de Ponto

Estratégia: Utiliza-se um array de diferenças. Armazenamos a diferença entre elementos consecutivos: diff[i] = arr[i] - arr[i - 1].

Atualização de intervalo: Para adicionar k ao intervalo [l, r], a diferença em l aumenta em k e a diferença em r+1 diminui em k.

inline void range_update(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}

Consulta de ponto: A soma das diferenças até a posição x retorna o valor do elemento na posição x.

Código de exemplo:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 5;
int n, q, arr[MAXN], tree[MAXN];

inline int lowbit(int x) { return x & (-x); }
inline void update(int pos, int val) {
    while (pos <= n) {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}
inline void range_update(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}
inline int query(int pos) {
    int res = 0;
    while (pos > 0) {
        res += tree[pos];
        pos -= lowbit(pos);
    }
    return res;
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        update(i, arr[i] - arr[i - 1]);
    }
    while (q--) {
        int op, l, r, val, x;
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> val;
            range_update(l, r, val);
        } else {
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

2. Atualização de Intervalo e Consulta de Ponto

Utilizamos um array de diferenças diff[i] = arr[i] - arr[i - 1]. A consulta em um ponto x é a soma das diferenças até x.

Para a atualização de intervalo, usamos a mesma lógica: update(l, val) e update(r + 1, -val).

3. Atualização de Intervalo e Consulta de Intervalo

Este caso exige o uso de quatro árvores de Fenwick para suportar a lógica de diferenças em duas dimensões, mantendo somas parciais para um cálculo eficiente de prefixos.

Fenwick Tree Bidimensional

1. Atualização de Ponto e Consulta de Intervalo

A consulta utiliza o princípio da inclusão-exclusão (Princípio da Casa dos Pombos).

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 5001;
int rows, cols;
int bit[MAX][MAX];

int lowbit(int x) { return x & -x; }

void update(int x, int y, int val) {
    for (int i = x; i <= rows; i += lowbit(i))
        for (int j = y; j <= cols; j += lowbit(j))
            bit[i][j] += val;
}

int query(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            res += bit[i][j];
    return res;
}

// Para consulta no retângulo (a,b) a (c,d):
// query(c, d) - query(a-1, d) - query(c, b-1) + query(a-1, b-1)

Fenwick Tree Bidimensional

1. Atualização de Ponto e Consulta de Intervalo

A consulta utiliza o princípio da inclusão-exclusão.

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5001;
int n, m;
int bit[MAXN][MAXN];

int lowbit(int x) { return x & -x; }

void update(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            bit[i][j] += val;
}

int query(int x, int y) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            sum += bit[i][j];
    return sum;
}

4. Atualização de Intervalo e Consulta de Ponto (2D)

Utilizamos o princípio da diferença bidimensional. Para adicionar k ao retângulo (a, b) a (c, d):

void range_update_2d(int a, int b, int c, int d, int k) {
    update(a, b, k);
    update(a, d + 1, -k);
    update(c + 1, b, -k);
    update(c + 1, d + 1, k);
}

5. Atualização de Intervalo e Consulta de Intervalo (2D)

Para suportar ambas as operações em 2D, precisamos de quatro árvores de Fenwick, mantendo as seguintes somas:

• d[i][j]
• d[i][j] * i
• d[i][j] * j
• d[i][j] * i * j

Isso permite calcular a soma do prefixo (x, y) usando a fórmula de expansão do somatório duplo.