Árvore de Fenwick / Árvore de Indexação Binária (BIT)

Vamos deixar com que $ f $ seja alguma função reversível e $A$ seja uma array de números inteiros de comprimento $N$.

A Árvore de Fenwick é uma estrutura de dados que:

Árvore de Fenwick é também chamada de Árvore de Indexação Binária, ou apenas BIT.

A aplicação mais comum da árvore Fenwick é calcular a soma de um range (i.e. $f(A_1, A_2, \dots, A_k) = A_1 + A_2 + \dots + A_k$).

A Árvore de Fenwick foi descrita pela primeira vez em um artigo intitulado "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

Descrição

Visão Geral

Por uma questão de simplicidade, assumiremos que a função $f$ é apenas uma função de soma.

Fornecida uma array $A[0 \dots N-1]$. Uma árvore de Fenwick é apenas uma array $T[0 \dots N-1]$, onde cada um de seus elementos é igual à soma dos elementos de $A$ em um range $[g(i); i]$: $$T_i = \sum_{j = g(i)}^{i}{A_j},$$ onde $g$ é uma função que satisfaz $0 \le g(i) \le i$. Definiremos a função nos próximos parágrafos.

A estrutura de dados é chamada de árvore, porque existe uma boa representação da estrutura de dados como árvore, embora não precisemos modelar uma árvore real com vértices e nós. Só precisamos manter a array $ T $ para lidar com todas as queries.

Nota: A Árvore de Fenwick apresentada aqui usa indexação baseada em 0([0,1,2..]). Muitas pessoas realmente usarão uma versão da Árvore de Fenwick que usa indexação baseada em um([1,2,3..]). Ambas as versões são equivalentes em termos de tempo e complexidade de memória.

Agora podemos escrever um pseudocódigo para as duas operações mencionadas acima - consiga a soma dos elementos de $A$ no range $[0; r]$ e atualizar (incrementar) algum 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 val):
    for all j with g(j) <= i <= j:
        t[j] += val

A função sum funciona da seguinte maneira:

  1. primeiro, adiciona a soma do intervalo $[g(r); r]$ (i.e. $T[r]$) para o resultado
  2. então, "salta" para o intervalo $[g(g(r)-1); g(r)-1]$, e adiciona a soma desse range ao resultado
  3. e assim por diante, até que "salte" de $[0; g(g( \dots g(r)-1 \dots -1)-1)]$ para $[g(-1); -1]$; é aí que a função sum para de saltar.

A função increase funciona na mesma analogia, mas "salta" na direção de aumentar os índices:

  1. Somas dos ranges $[g(j); j]$ que satisfaçam a condição $g(j) \le i \le j$ são incrementadas por delta , isto é t[j] += delta. Portanto, atualizamos todos os elementos em $T$ que corresponde a intervalos em que $A_i$ pertence.

É óbvio que a complexidade de ambos sum e increase dependem da função $g$. Existem várias maneiras de escolher a função $g$, enquanto $0 \le g(i) \le i$ para todo $i$. Por exemplo, a função $g(i) = i$ funciona, no que resulta $T = A$, e, portanto, as queries de soma são lentas. Também podemos assumir a função $g(i) = 0$. Isso corresponderá ao algoritmo da soma de prefixos de uma array, portanto achar a soma de um range $[0; i]$ será em tempo constante, mas atualizações serão lentas. Para o algoritmo, é fornecida uma array, você irá criar outra(array de prefixos), onde cada elemento será $pref[i] = pref[i-1] + a[i];$ e a soma do range $[j; i]$ corresponderá $pref[i] - pref[j-1]$, se $j = 0$ teremos soma $[0,i]$ correspondendo à $pref[i]$. A parte inteligente do algoritmo Fenwick é que ele usa uma definição especial da função $g$ que pode lidar com ambas as operações em tempo $O(\log N)$.

Definição de $g(i)$

O cálculo de $g(i)$ é definido pela operação: nós substituímos todos os $1$ bits à direita na representação binária de $i$ com $0$ bits.

Em outras palavras, se o dígito menos significativo de $i$ em binário é $0$, então $g(i) = i$. Ao contrário se for $1$, pegamos esse $1$ e todos os outros $1$s entrelados e trocamos eles.

Por exemplo, temos

$$\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 uma implementação simples usando operações bitwise para a operação descrita acima: $$g(i) = i ~\&~ (i+1),$$ onde $\&$ é o operador bitwise AND. Esta solução faz a mesma coisa que a operação descrita acima.

Para transformar uma string binária em um inteiro, podemos fazer com o seguinte código:

string s; int x = stoi(s, nullptr, 2); //stoi(string, size_t*, base do número(binário = 2))

Agora, só precisamos encontrar uma maneira de iterar sobre todos $j$'s, de tal modo que $g(j) \le i \le j$.

É fácil ver que podemos encontrar todos esses $j$'s começando com $i$ e trocando o último bit que não foi trocado ainda. Vamos chamar essa operação de $h(j)$. Por exemplo, para $i = 10$ teremos:

$$\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}$$

Também existe uma forma simples de executar $h$ usando operadores bitwise: $$h(j) = j ~|~ (j+1),$$ onde $|$ é o operador bitwise OR.

A imagem a seguir mostra uma possível interpretação da Árvore Fenwick como uma árvore. Os nós da árvore mostram o range em que eles cobrem.

Example BIT

Implementação

Encontrando a soma em uma array unidimensional

Aqui, apresentamos uma implementação da Árvore de Fenwick para queries de soma e atualizações individuais de elementos.

A Árvore de Fenwick normal só pode responder queries de soma do tipo $[0; r]$ usando sum(int r), no entanto, também podemos responder a outras queries do tipo $[l; r]$ calculando 2 somas $[0; r]$ e $[0; l-1]$ e subtraindo elas(como no algoritmo do prefixo da soma). Isso é lidado com o método sum(int l, int r).

Além disso, esta implementação suporta dois construtores. Você pode criar uma árvore de Fenwick iniciada apenas com zeros, ou você pode converter uma array existente na forma de Fenwick(lembre-se que trabalhar com a árvore de Fenwick, será trabalhar com operações em bits).

struct FenwickTree {
    vector<int> bit;  // arvore de indexaçao binaria
    int n;

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

    FenwickTree(vector<int> 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 val) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += val;
    }
};

Encontrando o mínimo de $[0; r]$ em uma array unidimensional

Não há uma maneira fácil de encontrar o mínimo do range $[l; r]$ usando Árvore de Fenwick, pois ela suporta queries do tipo $[0; r]$. Além disso, sempre que um valor é adicionado (update), o novo valor deve ser menor que o valor atual (porque a função $min$ não é reversível). Essas são limitações significativas.

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

    FenwickTreeMin(int n) {
        this->n = n;
        bit.assign(n, INF);  //{INF,INF,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 res = INF;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            res = min(res, bit[r]);
        return ret;
    }

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

Nota: é possível implementar uma árvore de Fenwick que possa lidar com consultas de range mínimo com atualizações(updates). O artigo "Queries de range mínimo eficientes com árvores de indexação binária" descreve essa ideia. No entanto, com essa abordagem, você precisa manter uma segunda árvore de indexação binária, com uma estrutura um pouco diferente, a primeira árvore não é suficiente para armazenar todos os elementos em uma array. The implementation is also a lot harder compared to the normal implementation for sums.

Encontrando a soma em uma array bidimensional

struct FenwickTree2D {
    vector<vector<int>> bit;   //arvore bit 2D
    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 val) {
        for (int i = x; i < n; i = i | (i + 1))
            for (int j = y; j < m; j = j | (j + 1))
                bit[i][j] += val;
    }
};

Abordagem de indexação

Para esta abordagem, alteramos os requisitos e a definição para $T[]$ e $g()$ um pouco. Queremos $T[i]$ para armazenar a soma de $[g(i)+1; i]$. Isso muda a implementação um pouco, e permite uma boa definição semelhante para $g(i)$:

def sum(int r):
    res = 0             
    while (r > 0):
        res += t[r]
        r = g(r)
    return res

def increase(int i, int val):
    for all j with g(j) < i <= j:
        t[j] += val

O calculo para $g(i)$ é definido como: alternando(XOR) o último bit set $1$ na representação binária de $i$.

$$\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}$$

O último bit set pode ser extraído $i ~\&~ (-i)$, a operação pode ser expressa: $$g(i) = i - (i ~\&~ (-i).$$

Você precisa alterar todos os valores $T[j]$ na sequência $i,~ h(i),~ h(h(i)),~ \dots$ quando você quiser atualizar $A[j]$, onde $h(i)$ é definido como: $$h(i) = i + (i ~\&~ (-i)).$$

Como você pode ver, o principal benefício dessa abordagem é que as operações binárias se complementam muito bem.

A implementação a seguir pode ser usada como as outras implementações, no entanto, usa indexação baseada em um internamente.

struct FenwickTreeOneBasedIndexing {
    vector<int> bit;  // binary indexed tree
    int n;

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

    FenwickTreeOneBasedIndexing(vector<int> a)
        : FenwickTreeOneBasedIndexing(a.size()) {
        init(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 val) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] += val;
    }
};

Operações em Range

A Árvore de Fenwick pode suportar as operações de range:

  1. update de um ponto e query de range
  2. update de um range e query de um ponto
  3. update de um range e query de um range

1. Update de um Ponto e query de Range

Árvore de Fenwick tradicional, explicada acima.

2. Update de Range e query de Ponto

Usando truques simples, também podemos fazer as operações inversas: aumentar ranges e fazer queries por valores individuais.

Deixe a Árvore Fenwick ser inicializada com zeros. Suponha que desejamos incrementar o intervalo $[l; r]$ com $x$. Fazemos 2 operações de update em pontos na Árvore de Fenwick na qual serão add(l, x) e add(r+1, -x).

Se queremos o valor de $A[i]$, só precisamos pegar a soma do prefixo usando o método do range de soma. Esse truque também é possível fazendo uma manipulação de arrays normal. Para ver por que isso é verdade, podemos focar apenas na operação de incremento anterior novamente. Se $i < l$, então as duas operações de update não tem efeito na query e temos a soma $0$. Se $i \in [l; r]$, então temos a resposta da soma $x$ por causa da primeira operação de update. E se $i > r$, a segunda operação (-x) irá cancelar o que a primeira operação fez (+x).

Implementação:

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

void range_add(int l, int r, int x) {
    add(l, x);
    add(r + 1, -x);
}

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

Nota: também é possível incrementar um único ponto $A[i]$ com range_add(i, i, x).

3. Updates em Range e query em Range

Para suportar ambos updates de range e queries de range usaremos duas BITs: $B_1[]$ e $B_2[]$, incicializadas com zeros.

Suponha que desejamos incrementar o intervalo $[l; r]$ com o valor $x$. Da mesma forma que no método anterior, realizamos 2 updates de pontos em $B_1$: add(B1, l, x) e add(B1, r+1, -x). E também fazemos um update em $B_2$.

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))

Depois do update no range $(l, r, x)$ a query de soma de range deve retornar os valores: $$ sum[0; i]= \begin{cases} 0 & i < l \\ x \cdot (i-(l-1)) & l \le i \le r \\ x \cdot (r-l+1) & i > r \\ \end{cases} $$

Podemos escrever a soma do intervalo como a diferença de dois termos, onde usamos $B_1$ para o primeiro termo e $B_2$ para o segundo termo. A diferença entre as queries nos dará o prefxo da soma sobre o range $[0; i]$. $$\begin{align} sum[0; i] &= sum(B_1, i) \cdot i - sum(B_2, i) \\ &= \begin{cases} 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{cases} \end{align} $$

Podemos usar $ B_2 $ para eliminar termos extras quando multiplicarmos $B_1[i]\times i$.

Podemos encontrar somas de intervalo calculando as somas de prefixo para $l-1$ e $r$ e tomando a diferença deles novamente.

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

Outros recursos