Informática Estruturas de Dados - Binary Indexed Tree (BIT) - Introdução à BIT

Aula por Lúcio Cardoso

Imagine que é dado um vetor $V$ com $N$ números inteiros, e precisamos realizar as seguintes operações:

1. Somar o valor $v$ no elemento de índice $x$ do vetor
2. Calcular a soma dos valores de índice no intervalo $[l, r]$

Nessa aula, será apresentada a esturutura de dados BIT, que consegue realizar as duas operações acima com complexidade $O(\log_{} N)$.

Descrição da estrutura

Inicialmente, vamos definir o bit menos significativo de um número inteiro $x$. Denote este valor por $lsb(x)$. $lsb(x)$ é igual ao bit ligado (igual a 1) mais à direita na representação binária de $x$. Por exemplo, como $6 = 110_2$, $lsb(6) = 1$. No C++, conseguimos encontrar $lsb(x)$ usando a expressão $x \& (-x)$, onde $\&$ representa o $and$ binário.

A BIT (Binary Indexed Tree) é um vetor de mesmo tamanho que $V$. Denotaremos o vetor da BIT por $bit[]$. Esta estrutura é construida tal que, para um índice $i$ ($1 \leq i \leq N$), $bit[i]$ é igual a soma de todos os elementos do vetor no intervalo $[i-2^{lsb(i)}+1, i]$, Ou seja,

$bit[i] = \sum_{k = i-2^{lsb(i)}+1}^i V[k]$.

Como um exemplo, se $V = [1, 0, 2, 4, -1]$, o vetor $bit$ será igual a $[1, 1, 2, 7, -1]$.

Função $upd(x, v)$

Esta função adiciona o valor $v$ na posição $x$ do vetor. Vamos pensar em como utilizar a BIT para realizar esta operação em $O(\log_{} N)$. Para isso, precisamos pensar em quais índices $i$ são tais que $bit[i]$ será alterado, ou seja, tais que $x$ esteja no intervalo $[i-2^{lsb(j)}+1, i]$.

Perceba que o intervalo de um índice $i < x$ certamente não contém $x$. Logo, o índice $x$ é o primeiro índice do vetor $bit[]$ que será alterado. Note também que o próximo índice a ser alterado, ou seja, o menor índice maior que $x$ alterado, será $x + 2^{lsb(x)}$, já que para qualquer inteiro $y < 2^{lsb(x)}$, o intervalo $[(x+y)-2^{lsb(x+y)}+1, x+y]$ certamente não contém $x$ (verifique!). Assim, o próximo índice que será alterado será $(x + 2^{lsb(x)}) + 2^{lsb(x+2^{lsb(x)})}$, e assim por diante. Dessa forma, chegamos que os índices do vetor $bit[]$ que serão somados em $v$ serão os seguintes:

$x \rightarrow x+2^{lsb(x)} \rightarrow (x+2^{lsb(x)}) + 2^{lsb(x+2^{lsb(x)})} \rightarrow ...$, até chegarmos no último número da lista menor ou igual a $N$.

Perceba que a lista acima possui no máximo $\log_{} N$ índices, pois as potências de $2$ somadas em cada valor (por exemplo, $2^{lsb(x)}$) são todas distintas (já que a lista possui valores estritamente crescentes), e há no máximo $\log_{} N$ potências de $2$ distintas menores ou iguais a $N$. Portanto, a complexidade da função $upd(x, v)$ é $O(\log_{} N)$. Segue o código abaixo para melhor entendimento:

Função $soma(x)$

A função $soma(x)$ calcula, utilizando a BIT, a soma de todos os números em $V$ de $1$ a $x$. Note, assim, que a soma dos valores no intervalo $[l, r]$ será $soma(r)-soma(l-1)$.

Inicialmente, possuímos a soma dos valores no intervalo $[x-2^{lsb(x)}+1, x]$, já calculada, pois esta soma é igual a $bit[x]$. Além disso, também possuímos a soma do intervalo $[x-2^{lsb(x)}-2^{lsb(x-2^{lsb(x)})}+1, x-2^{lsb(x)}]$, que é exatamente $bit[x-2^{lsb(x)}]$.

Seguindo este processo, eventualmente vamos conseguir particionar o intervalo $[1, x]$ em intervalos menores e disjuntos, e assim, obter a sua soma. Portanto, vamos realizar o seguinte algoritmo:

1. Somar $bit[x]$ em nossa variável de resposta
2. Subtrair $2^{lsb(x)}$ de $x$
3. Repetir a etapa $1$ enquanto $x > 0$.

Pelo mesmo argumento usado na função $upd(x, v)$, é possível perceber que o algoritmo acima realizará no máximo $O(\log_{} N)$ operações. Confira o código para melhor entendimento:

Problemas para praticar

A estrutura de dados BIT pode ser usada para resolver diversos problemas. Pense nos problemas na lista abaixo:

• Arranha-Céu
• Range Sum Queries II
• Bolhas e Baldes
• Produto do Intervalo
• Balé