Mise à jour de l'étape de Fenwick Trees

Question

Ma question porte sur le raisonnement complet qui sous-tend l'étape de mise à jour dans les arbres indexés binaires (arbres de Fenwick). Ainsi, lors de la mise à jour de notre tableau avec un certain incrément, à une certaine position, la mise à jour se déroule comme suit :

void updateBIT(int BITree[], int n, int index, int val)
{
    // index in BITree[] is 1 more than the index in arr[]
    index = index + 1;

    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;

       // Update index to that of parent in update View
       index += index & (-index);
    }

Mon problème se situe au niveau de la index += index & (-index); partie. Veuillez noter que je comprends la index & (-index) surtout dans le contexte de l'interrogation de l'arbre.

J'ai essayé plusieurs exemples à la main en utilisant cette règle de mise à jour de l'index, mais je n'ai pas réussi à trouver la logique derrière l'ajout de index & (-index) afin de passer au nœud suivant qui doit être mis à jour.

D'après ce que j'ai obtenu jusqu'à présent, un nœud i dans un BIT est "responsable" des valeurs originales dans le tableau allant de [i - i & (-i) + 1, i] ce qui implique que tout nœud se trouve dans un intervalle de cette forme. Plus précisément, si j'ai bien compris, lorsque l'on veut mettre à jour la position k dans le tableau original, nous suivons les étapes suivantes (conceptuellement, pas dans le code réel) :

• Itération 0 : mise à jour BIT[k + 1] (les indices sont décalés de 1 dans le BIT). Alors que l'on est toujours à l'itération 0 Nous mettons à jour l'index que nous sommes en train d'élaborer. donc je suppose que nous recherchons le prochain plus petit intervalle responsable du nœud k Nous devons donc trouver la indice suivant i donde i - i & (-i) < k < i . Trouver cet index i par en incrémentant l'indice actuel de k & (-k) .

Les autres itérations se déroulent de la même manière jusqu'à ce que nous sortions des limites. J'ai essayé de nombreux exemples à la main, et je ne comprends toujours pas pourquoi l'ajout de i & (-i) nous amène au nœud suivant. Tous les tutoriels que j'ai trouvés sur le web, y compris les vidéos, sont complètement douteux à ce sujet.

Plusieurs questions relatives aux TBI sont posées ici, veuillez ne pas les fusionner avec les miennes avant de les avoir lues attentivement . A ma connaissance, cette question n'a pas reçu de réponse.

Answer 1

Je vais donc tenter d'expliquer le scénario ci-dessus en prenant un exemple simple.

Prenons i = 12 . Maintenant, nous mettons à jour BIT[12] . Selon l'algorithme, l'étape suivante de la mise à jour est la suivante i += i&(-i) .

Que représente 12 en binaire = 01100 . Le dernier bit défini est 2 , la valeur est de 2^2 = 4 (comme vous le savez

0th bit value is 2^0 = 1
1st bit value is 2^1 = 2
2nd bit value is 2^2 = 4.

Il en va de même pour les autres bits.

Le prochain index que nous mettrons à jour est donc 12 + 4 = 16 . i.e BIT[16] .

Il s'agissait de savoir comment le système fonctionne. Permettez-moi d'essayer d'expliquer en termes simples pourquoi cette technique fonctionne.

Supposons que je doive mettre à jour index = 1 et disons que la valeur du tableau MAX est 8. Alors, quel est l'index que je vais mettre à jour ? 1,2,4,8 .

Supposons maintenant que je doive mettre à jour index = 3 . Je dois donc mettre à jour les index du tableau 3,4,8 .

Vous voyez donc comment, jusqu'à présent BIT[4] a obtenu la somme de toutes les valeurs de l'index du tableau 1 to 4 .

Supposons maintenant que vous souhaitiez obtenir la somme totale des 4 premiers nombres, il vous suffit de faire BIT[4] et vous traverserez les index 4,0 . En bref, vous ne traversez pas 1,2,3 . Comme nous l'avons vu, ces indices ont été couverts en raison de la manipulation des bits.

J'espère que cela vous aidera !