Le tableau original "A"(indice commence de 0):
4 4 7 4 12 0 0 3 3 3 0 0 3 0 3 0 0 5 0 0

L'arbre de Fenwick "ft": (indice commence de 0)
0 4 8 7 19 12 12 0 34 3 6 0 6 3 3 3 46 0 5 0 5

Comment calculer la somme des éléments suivant en utilisant l'arbre de Fenwick en O(log N) ?
A[9] + A[3]+ A[10] + A[8] + A[13] + A[5] + A[15]

Ma proposition : O(N log N)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
fonction sommeFenwick(int i)
  s = 0
  pour(++i ; i > 0 ; i -= i & -i)
    s += ft[i]
  fin pouri
 
  retounrer s
fin sommeFenwick
 
//Programme principal O(N * 2 * log N)
indices = {9,3,10,8,13,5,15}
pour chaque i dans indices faire
   som += sommeFenwick(i) - sommFenwick(i-1)
fin pouri
 
afficher(som)
La fonction "sommeFenwick" est de complexité O(log N).


On peut, ne pas utiliser un arbre de Fenwick:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
//Dans le pire des cas O(N)
indices = {9,3,10,8,13,5,15}
pour chaque i dans indices faire
   som += A[i]
fin pouri
Ici, on ne peut pas utiliser un tableau de somme cumulatif, parce que le tableau "A" est mis à jour durant l'éxécution.

Comment faire cette somme en O(log N) en utilisant l'arbre de Fenwick ?

Merci