Discussion :

[blackbird1]

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

[bm]

Faudrait donner l'énoncé papier et les questions du problème ..

[anapurna]

salut

l'arbre de fenwick ce sert des propriété de puissance de 2 qu'utilise les arbre binaire
tu ne peut pas utiliser ton tableau d'indice en état il faut que tu recréer ton arbre avant de pouvoir en faire la somme

pour faire simple

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
  // Prochain
   int getNext(int index){
        return index + (index & -index);
    }
 
  // Precedent ou parent
   int getParent(int index){
        return index - (index & -index);
    }
 
 
  int[] createTree(int input[])
  {  int IntbinaryIndexedTree[] = new int[input.length+1]; // on donne la taille da la structure passé en paramètre
        for(int i=1; i <= input.length; i++) // on parcourt la tableau passé en paramètre
        {    updateBinaryIndexedTree(IntbinaryIndexedTree, input[i-1], i); // on met a jour le nouvel arbre
        }
        return IntbinaryIndexedTree;
    }
 
   void updateBinaryIndexedTree(int binaryIndexedTree[], int val, int index)
  {  while(index < binaryIndexedTree.length)
     {  binaryIndexedTree[index] += val; // on cumul les valeur de l'arbre
         index = getNext(index);
      }
   }
 
  int getSum(int binaryIndexedTree[], int index)
  {  index = index + 1;
      int sum = 0;
      while(index > 0)
     {
         sum += binaryIndexedTree[index];
         index = getParent(index);
     }
     return sum;
    }

[blackbird1]

Le problème de hacherrank:
set-queries-English.pdf

Ma solution C++ qui dépasse la limite de temps:
c.cpp

Merci