BIT: Qual é a intuição por trás de uma árvore indexada binária e como foi pensada?

Uma árvore indexada binária tem muito menos ou relativamente nenhuma literatura em comparação com outras estruturas de dados. O único lugar em que é ensinado é o tutorial do codificador topográfico . Embora o tutorial esteja completo em todas as explicações, não consigo entender a intuição por trás dessa árvore? Como foi inventado? Qual é a prova real de sua correção?

Intuitivamente, você pode pensar em uma árvore indexada binária como uma representação compactada de uma árvore binária que é ela própria uma otimização de uma representação de matriz padrão. Essa resposta entra em uma derivação possível.

Vamos supor, por exemplo, que você deseja armazenar frequências cumulativas para um total de 7 elementos diferentes. Você pode começar escrevendo sete blocos nos quais os números serão distribuídos:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Agora, vamos supor que as frequências cumulativas sejam mais ou menos assim:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Usando esta versão do array, você pode incrementar a frequência cumulativa de qualquer elemento aumentando o valor do número armazenado naquele local e, em seguida, incrementando as frequências de tudo o que vem depois. Por exemplo, para aumentar a frequência cumulativa de 3 em 7, poderíamos adicionar 7 a cada elemento na matriz na ou após a posição 3, conforme mostrado aqui:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

O problema é que leva O (n) tempo para fazer isso, o que é bastante lento se n for grande.

Uma maneira de pensar em melhorar essa operação seria alterar o que armazenamos nos baldes. Em vez de armazenar a frequência cumulativa até o ponto especificado, você pode pensar em apenas armazenar a quantidade que a frequência atual aumentou em relação ao intervalo anterior. Por exemplo, no nosso caso, reescreveríamos os buckets acima da seguinte maneira:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

Agora, podemos incrementar a frequência dentro de um intervalo no tempo O (1) apenas adicionando a quantidade apropriada a esse intervalo. No entanto, o custo total de fazer uma pesquisa agora se torna O (n), uma vez que temos que recalcular o total no intervalo, somando os valores em todos os intervalos menores.

O primeiro insight importante que precisamos obter daqui para uma árvore indexada binária é o seguinte: em vez de recalcular continuamente a soma dos elementos da matriz que precedem um elemento específico, e se precompuséssemos a soma total de todos os elementos antes de especificar pontos na sequência? Se pudéssemos fazer isso, poderíamos descobrir a soma cumulativa em um ponto apenas resumindo a combinação certa dessas somas pré-computadas.

Uma maneira de fazer isso é alterar a representação de uma matriz de buckets para uma árvore binária de nós. Cada nó será anotado com um valor que representa a soma cumulativa de todos os nós à esquerda desse nó. Por exemplo, suponha que construamos a seguinte árvore binária a partir desses nós:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Agora, podemos aumentar cada nó armazenando a soma cumulativa de todos os valores, incluindo esse nó e sua subárvore esquerda. Por exemplo, dados nossos valores, armazenaríamos o seguinte:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

Dada essa estrutura em árvore, é fácil determinar a soma acumulada até um ponto. A idéia é a seguinte: mantemos um contador, inicialmente 0, e fazemos uma pesquisa binária normal até encontrar o nó em questão. Ao fazer isso, também fazemos o seguinte: sempre que movemos para a direita, também adicionamos o valor atual ao contador.

Por exemplo, suponha que desejamos procurar a soma de 3. Para fazer isso, fazemos o seguinte:

• Comece pela raiz (4). O contador é 0.
• Vá para a esquerda no nó (2). O contador é 0.
• Vá para a direita no nó (3). O contador é 0 + 6 = 6.
• Encontre o nó (3). O contador é 6 + 15 = 21.

Você também pode imaginar executando esse processo ao contrário: começando em um determinado nó, inicialize o contador com o valor desse nó e suba a árvore até a raiz. Sempre que você seguir um link filho certo para cima, adicione o valor no nó em que você chega. Por exemplo, para encontrar a frequência de 3, poderíamos fazer o seguinte:

• Comece no nó (3). O contador é 15.
• Vá para cima para o nó (2). O contador é 15 + 6 = 21.
• Vá para cima para o nó (4). O contador é 21.

Para aumentar a frequência de um nó (e, implicitamente, as frequências de todos os nós que vêm depois dele), precisamos atualizar o conjunto de nós na árvore que inclui esse nó na subárvore esquerda. Para fazer isso, faça o seguinte: aumente a frequência desse nó e comece a caminhar até a raiz da árvore. Sempre que você seguir um link que o levará como filho esquerdo, aumente a frequência do nó encontrado, adicionando o valor atual.

Por exemplo, para aumentar a frequência do nó 1 em cinco, faríamos o seguinte:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

Começando no nó 1, aumente sua frequência em 5 para obter

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

Agora, vá para o pai:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Como seguimos um link filho esquerdo para cima, aumentamos a frequência desse nó:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Agora vamos ao seu pai:

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

Como era um link filho esquerdo, também incrementamos esse nó:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

E agora terminamos!

O passo final é converter isso em uma árvore indexada binária, e é aqui que podemos fazer coisas divertidas com números binários. Vamos reescrever cada índice de bucket nesta árvore em binário:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Aqui, podemos fazer uma observação muito, muito legal. Pegue qualquer um desses números binários e encontre o último 1 que foi definido no número, depois solte esse bit, juntamente com todos os bits que vierem depois dele. Agora você tem o seguinte:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Aqui está uma observação muito, muito legal: se você tratar 0 como "esquerdo" e 1 como "direito", os bits restantes em cada número explicam exatamente como começar na raiz e depois caminhar até esse número. Por exemplo, o nó 5 possui o padrão binário 101. O último 1 é o bit final, então deixamos cair esse número para obter 10. De fato, se você começar pela raiz, vá para a direita (1) e depois para a esquerda (0) e finalize no nó 5!

O motivo disso ser significativo é que nossas operações de pesquisa e atualização dependem do caminho de acesso do nó de volta à raiz e se estamos seguindo os links filhos esquerdo ou direito. Por exemplo, durante uma pesquisa, apenas nos preocupamos com os links certos que seguimos. Durante uma atualização, apenas nos preocupamos com os links à esquerda que seguimos. Essa árvore indexada binária faz tudo isso de maneira super eficiente usando apenas os bits no índice.

O truque principal é a seguinte propriedade dessa árvore binária perfeita:

Dado o nó n, o próximo nó no caminho de acesso de volta à raiz na qual vamos para a direita é dado pegando a representação binária de n e removendo o último 1.

Por exemplo, dê uma olhada no caminho de acesso para o nó 7, que é 111. Os nós no caminho de acesso à raiz que usamos que envolvem seguir um ponteiro direito para cima são

• Nó 7: 111
• Nó 6: 110
• Nó 4: 100

Todos esses são links corretos. Se pegarmos o caminho de acesso para o nó 3, que é 011, e olharmos para os nós onde damos certo, obtemos

• Nó 3: 011
• Nó 2: 010
• (Nó 4: 100, que segue o link esquerdo)

Isso significa que podemos computar de maneira muito, muito eficiente a soma acumulada em um nó da seguinte maneira:

• Escreva o nó n em binário.
• Defina o contador como 0.
• Repita o seguinte enquanto n ≠ 0:
  • Adicione o valor no nó n.
  • Limpe o bit 1 à direita de n.

Da mesma forma, vamos pensar em como faríamos uma etapa de atualização. Para fazer isso, gostaríamos de seguir o caminho de acesso de volta à raiz, atualizando todos os nós nos quais seguimos um link esquerdo para cima. Podemos fazer isso essencialmente executando o algoritmo acima, mas alternando todos os 1 para 0 e 0 para 1.

A etapa final na árvore indexada binária é observar que, devido a esse truque bit a bit, nem precisamos mais armazenar a árvore explicitamente. Podemos simplesmente armazenar todos os nós em uma matriz de comprimento n e, em seguida, usar as técnicas de twittling bit a bit para navegar implicitamente na árvore. De fato, é exatamente isso que a árvore indexada bit a bit faz - ela armazena os nós em uma matriz e usa esses truques bit a bit para simular com eficiência a subida nessa árvore.

Espero que isto ajude!

Eu acho que o artigo original de Fenwick é muito mais claro. A resposta acima de @templatetypedef requer algumas "observações muito legais" sobre a indexação de uma árvore binária perfeita, que são confusas e mágicas para mim.

Fenwick simplesmente disse que o alcance da responsabilidade de cada nó na árvore de interrogação estaria de acordo com seu último bit definido:

Por exemplo, como o último bit definido de 6== 00110é um "2 bits", ele será responsável por um intervalo de 2 nós. Para 12== 01100, é um "4 bits", por isso será responsável por um intervalo de 4 nós.

Portanto, ao consultar F(12)== F(01100), removemos os bits um por um, obtendo F(9:12) + F(1:8). Isso não é quase uma prova rigorosa, mas acho que é mais óbvio quando colocado de maneira simples no eixo dos números e não em uma árvore binária perfeita, quais são as responsabilidades de cada nó e por que o custo da consulta é igual ao número de definir bits.

Se isso ainda não estiver claro, o papel é muito recomendado.