Mise à jour de plage + requête de plage avec des arbres indexés binaires

J'essaie de comprendre comment les arbres indexés binaires (arbres fenwick) peuvent être modifiés pour gérer à la fois les requêtes de plage et les mises à jour de plage.

J'ai trouvé les sources suivantes:

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 = Thread & threadID = 756271 & start = 0 & mc = 4 # 1579597

Mais même après les avoir lus tous, je ne pouvais pas comprendre quel était le but du deuxième arbre indexé binaire ou ce qu'il faisait.

Quelqu'un pourrait-il m'expliquer comment l'arbre binaire indexé est modifié pour les gérer?

Supposons que vous disposiez d'un tableau vide:

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

Et vous vouliez faire une mise à jour de la plage de +5 à [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)

Comment pouvez-vous stocker les sommes cumulées souhaitées à l'aide de 2 arbres indexés binaires?

L'astuce consiste à utiliser deux arbres indexés binaires, BIT1 et BIT2, où la somme cumulée est calculée à partir de leur contenu. Dans cet exemple, voici ce que nous stockons dans les deux arbres:

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

Pour trouver sum[i], vous calculez ceci:

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

Par exemple:

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

Pour atteindre les valeurs BIT1 et BIT2 souhaitées pour la mise à jour de la plage précédente, nous effectuons 3 mises à jour de la plage:

• Nous devons faire une mise à jour de la plage de +5 aux indices 3..7 pour BIT1.

• Nous devons faire une mise à jour de la plage de +10 aux indices 3..7 pour BIT2.

• Nous devons faire une mise à jour de la plage de -25 aux indices 8..9 pour BIT2.

Faisons maintenant une autre transformation. Au lieu de stocker les valeurs indiquées ci-dessus pour BIT1 et BIT2, nous stockons en fait leurs sommes cumulées. Cela nous permet de faire les 3 mises à jour de gamme ci-dessus en faisant 4 mises à jour des sommes cumulées:

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

En général, l'algorithme pour ajouter une valeur v à une plage [i..j] serait:

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

où la syntaxe + = et - = signifie simplement mettre à jour la structure de données de somme cumulée BIT avec une valeur positive ou négative à cet indice. Notez que lorsque vous mettez à jour la somme cumulée BIT à un index, cela affecte implicitement tous les indices à droite de cet index. Par exemple:

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(\log n)$