Aula por Lúcio Cardoso
Imagine que é dado um vetor $$V$$ com $$N$$ números inteiros, e precisamos realizar as seguintes operações:
- Somar o valor $$v$$ no elemento de índice $$x$$ do vetor
- 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:
https://gist.github.com/luciocf/0d2b854944bf814b9f0eee7ebda6684f
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:
- Somar $$bit[x]$$ em nossa variável de resposta
- Subtrair $$2^{lsb(x)}$$ de $$x$$
- 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:
https://gist.github.com/luciocf/bf15199e5dd678a15b9cfb14061a86b2
Problemas para praticar
A estrutura de dados BIT pode ser usada para resolver diversos problemas. Pense nos problemas na lista abaixo: