Atualização de intervalo + consulta de intervalo com árvores indexadas binárias

10

Estou tentando entender como as árvores indexadas binárias (árvores fenwick) podem ser modificadas para lidar com consultas e atualizações de intervalo.

Encontrei as seguintes fontes:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http : //apps.topcoder.com/forums/? module = ThreadID da thread & = 756271 & start = 0 & mc = 4 # 1579597

Mas, mesmo depois de ler todos eles, eu não conseguia entender qual é o objetivo da segunda árvore indexada binária ou o que ela faz.

Alguém poderia me explicar como a árvore indexada binária é modificada para lidar com isso?

1110101001
fonte

Respostas:

9

Suponha que você tenha uma matriz vazia:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

E você queria fazer uma atualização de intervalo de +5 a [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

Como você pode armazenar as somas cumulativas desejadas usando duas árvores indexadas binárias?

O truque é usar duas árvores indexadas binárias, BIT1 e BIT2, onde a soma cumulativa é calculada a partir do seu conteúdo. Neste exemplo, aqui está o que armazenaríamos nas duas árvores:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

Para encontrar sum[i], você calcula isso:

sum[i] = BIT1[i] * i - BIT2[i]

Por exemplo:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

Para atingir os valores BIT1 e BIT2 desejados para a atualização anterior do intervalo, fazemos três atualizações de intervalo:

  • Precisamos fazer uma atualização de intervalo de +5 nos índices 3..7 para o BIT1.

  • Precisamos fazer uma atualização de intervalo de +10 nos índices 3..7 para o BIT2.

  • Precisamos fazer uma atualização de intervalo de -25 aos índices 8..9 para o BIT2.

Agora vamos fazer mais uma transformação. Em vez de armazenar os valores mostrados acima para o BIT1 e o BIT2, na verdade armazenamos suas somas cumulativas. Isso nos permite fazer as 3 atualizações de intervalo acima, fazendo 4 atualizações nas somas cumulativas:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

Em geral, o algoritmo para adicionar um valor v a um intervalo [i..j] seria:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

onde a sintaxe + = e - = significa simplesmente atualizar a estrutura de dados de soma acumulada BIT com um valor positivo ou negativo nesse índice. Observe que quando você atualiza a soma acumulada do BIT em um índice, isso afeta implicitamente todos os índices à direita desse índice. Por exemplo:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

O(registron)

JS1
fonte
Qual foi a sua motivação inicial para criar o BIT2 e depois ter sum[i] = BIT1[i] * i - BIT2[i]? Parece funcionar, mas parece tão arbitrário ... que insight permite que você chegue a isso?
1110101001
3
Bem, eu não inventei esse algoritmo. Eu li como você. Mas uma coisa a ser observada é que, quando você adiciona uma atualização de intervalo, suas somas cumulativas se tornam uma sequência crescente (5, 10, 15, 20, ...). Os BITs não armazenam sequências crescentes como essa. Mas se você armazenar uma constante (5) no BIT e multiplicar o valor do BIT pelo índice, obterá uma sequência crescente exatamente como você deseja. No entanto, você precisa corrigir o início e o fim da sequência. É para isso que serve a segunda árvore.
JS1
Bom no geral, mas achei confuso que você tenha escrito "Em vez de armazenar os valores mostrados acima para o BIT1 e o BIT2, na verdade armazenamos suas somas cumulativas" - eu diria que você está realmente fazendo o contrário, ou seja, armazenando os deltas .
Jrandom_hacker