Consideriamo il seguente problema per comprendere l'albero indicizzato binario.
Abbiamo un array arr[0 . . . n-1]. Ci piacerebbe
1 Calcola la somma dei primi i elementi.
2 Modifica il valore di un elemento specificato dell'array arr[i] = x dove 0 <= i <= n-1.
UN soluzione semplice consiste nell'eseguire un ciclo da 0 a i-1 e calcolare la somma degli elementi. Per aggiornare un valore, basta semplicemente arr[i] = x. La prima operazione richiede tempo O(n) e la seconda operazione richiede tempo O(1). Un'altra soluzione semplice è creare un array aggiuntivo e memorizzare la somma dei primi i-esimi elementi nell'i-esimo indice in questo nuovo array. La somma di un determinato intervallo può ora essere calcolata in tempo O(1), ma l'operazione di aggiornamento ora richiede tempo O(n). Funziona bene se è presente un numero elevato di operazioni di query ma un numero molto limitato di operazioni di aggiornamento.
Potremmo eseguire sia le operazioni di query che quelle di aggiornamento in tempo O (log n)?
Una soluzione efficiente consiste nell'utilizzare Segment Tree che esegue entrambe le operazioni in tempo O(Logn).
Una soluzione alternativa è l'albero indicizzato binario, che raggiunge anche la complessità temporale O(Logn) per entrambe le operazioni. Rispetto all'albero dei segmenti, l'albero indicizzato binario richiede meno spazio ed è più facile da implementare. .
Rappresentazione
L'albero indicizzato binario è rappresentato come un array. Lascia che l'array sia BITree[]. Ciascun nodo dell'albero indicizzato binario memorizza la somma di alcuni elementi dell'array di input. La dimensione dell'albero indicizzato binario è uguale alla dimensione dell'array di input, indicato come n. Nel codice seguente utilizziamo la dimensione n+1 per facilitare l'implementazione.
Costruzione
Inizializziamo tutti i valori in BITree[] come 0. Quindi chiamiamo update() per tutti gli indici, l'operazione update() è discussa di seguito.
Operazioni
getSum(x): restituisce la somma del sottoarray arr[0,…,x]
// Restituisce la somma del sottoarray arr[0,…,x] utilizzando BITree[0..n], che è costruito da arr[0..n-1]
1) Inizializzare la somma dell'output come 0, l'indice corrente come x+1.
2) Eseguire quanto segue mentre l'indice corrente è maggiore di 0.
…a) Aggiungi BITree[indice] alla somma
…b) Vai al genitore di BITree[indice]. Il genitore può essere ottenuto rimuovendo
l'ultimo bit impostato dall'indice corrente, ovvero indice = indice – (indice & (-indice))
3) Restituire la somma.
Il diagramma sopra fornisce un esempio di come funziona getSum(). Ecco alcune osservazioni importanti.
BITree[0] è un nodo fittizio.
BITree[y] è il genitore di BITree[x], se e solo se y può essere ottenuto rimuovendo l'ultimo bit impostato dalla rappresentazione binaria di x, ovvero y = x – (x & (-x)).
Il nodo figlio BITree[x] del nodo BITree[y] memorizza la somma degli elementi compresi tra y(inclusive) e x(exclusive): arr[y,…,x).
update(x, val): aggiorna l'albero indicizzato binario (BIT) eseguendo arr[index] += val
// Nota che l'operazione update(x, val) non modificherà arr[]. Apporta modifiche solo a BITree[]
1) Inizializza l'indice corrente come x+1.
2) Effettuare le seguenti operazioni mentre l'indice corrente è inferiore o uguale a n.
…a) Aggiungi val a BITree[indice]
…b) Vai all'elemento successivo di BITree[indice]. L'elemento successivo può essere ottenuto incrementando l'ultimo bit impostato dell'indice corrente, ovvero indice = indice + (indice & (-indice))
La funzione di aggiornamento deve assicurarsi che tutti i nodi BITree che contengono arr[i] nei loro intervalli vengano aggiornati. Eseguiamo il loop su tali nodi nel BITree aggiungendo ripetutamente il numero decimale corrispondente all'ultimo bit impostato dell'indice corrente.
Come funziona l'albero indicizzato binario?
L'idea si basa sul fatto che tutti gli interi positivi possono essere rappresentati come la somma di potenze di 2. Ad esempio 19 può essere rappresentato come 16 + 2 + 1. Ogni nodo del BITree memorizza la somma di n elementi dove n è un potenza di 2. Ad esempio, nel primo diagramma qui sopra (il diagramma per getSum()), la somma dei primi 12 elementi può essere ottenuta dalla somma degli ultimi 4 elementi (da 9 a 12) più la somma di 8 elementi (da 1 a 8). Il numero di bit impostati nella rappresentazione binaria di un numero n è O(Logn). Pertanto, attraversiamo al massimo i nodi O(Logn) in entrambe le operazioni getSum() e update(). La complessità temporale della costruzione è O(nLogn) poiché chiama update() per tutti gli n elementi.
Implementazione:
Di seguito sono riportate le implementazioni dell'albero indicizzato binario.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->N. di elementi presenti nell'array di input.> >BITree[0..n] -->Matrice che rappresenta l'albero indicizzato binario.> >arr[0..n-1] -->Matrice di input per la quale viene valutata la somma dei prefissi. */> > // Returns sum of arr[0..index]. This function assumes> // that the array is preprocessed and partial sums of> // array elements are stored in BITree[].> int> getSum(>int> BITree[],>int> index)> {> >int> sum = 0;>// Initialize result> > >// index in BITree[] is 1 more than the index in arr[]> >index = index + 1;> > >// Traverse ancestors of BITree[index]> >while> (index>0)> >{> >// Add current element of BITree to sum> >sum += BITree[index];> > >// Move index to parent node in getSum View> >index -= index & (-index);> >}> >return> sum;> }> > // Updates a node in Binary Index Tree (BITree) at given index> // in BITree. The given value 'val' is added to BITree[i] and> // all of its ancestors in tree.> 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);> >}> }> > // Constructs and returns a Binary Indexed Tree for given> // array of size n.> int> *constructBITree(>int> arr[],>int> n)> {> >// Create and initialize BITree[] as 0> >int> *BITree =>new> int>[n+1];> >for> (>int> i=1; i<=n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[] using update()> >for> (>int> i=0; i updateBIT(BITree, n, i, arr[i]); // Uncomment below lines to see contents of BITree[] //for (int i=1; i<=n; i++) // cout << BITree[i] << ' '; return BITree; } // Driver program to test above functions int main() { int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = sizeof(freq)/sizeof(freq[0]); int *BITree = constructBITree(freq, n); cout << 'Sum of elements in arr[0..5] is ' << getSum(BITree, 5); // Let use test the update operation freq[3] += 6; updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[] cout << '
Sum of elements in arr[0..5] after update is ' << getSum(BITree, 5); return 0; }> |
età di pete davidson
>
>
Giava
// Java program to demonstrate lazy> // propagation in segment tree> import> java.util.*;> import> java.lang.*;> import> java.io.*;> > class> BinaryIndexedTree> {> >// Max tree size> >final> static> int> MAX =>1000>;> > >static> int> BITree[] =>new> int>[MAX];> > >/* n -->N. di elementi presenti nell'array di input.> >BITree[0..n] -->Matrice che rappresenta Binary> >Indexed Tree.> >arr[0..n-1] -->Array di input per il quale prefisso somma> >is evaluated. */> > >// Returns sum of arr[0..index]. This function> >// assumes that the array is preprocessed and> >// partial sums of array elements are stored> >// in BITree[].> >int> getSum(>int> index)> >{> >int> sum =>0>;>// Initialize result> > >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index +>1>;> > >// Traverse ancestors of BITree[index]> >while>(index>>0>)> >{> >// Add current element of BITree> >// to sum> >sum += BITree[index];> > >// Move index to parent node in> >// getSum View> >index -= index & (-index);> >}> >return> sum;> >}> > >// Updates a node in Binary Index Tree (BITree)> >// at given index in BITree. The given value> >// 'val' is added to BITree[i] and all of> >// its ancestors in tree.> >public> static> void> updateBIT(>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 BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> >}> > >/* Function to construct fenwick tree> >from given array.*/> >void> constructBITree(>int> arr[],>int> n)> >{> >// Initialize BITree[] as 0> >for>(>int> i=>1>; i<=n; i++)> >BITree[i] =>0>;> > >// Store the actual values in BITree[]> >// using update()> >for>(>int> i =>0>; i updateBIT(n, i, arr[i]); } // Main function public static void main(String args[]) { int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = freq.length; BinaryIndexedTree tree = new BinaryIndexedTree(); // Build fenwick tree from given array tree.constructBITree(freq, n); System.out.println('Sum of elements in arr[0..5]'+ ' is '+ tree.getSum(5)); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated System.out.println('Sum of elements in arr[0..5]'+ ' after update is ' + tree.getSum(5)); } } // This code is contributed by Ranjan Binwani> |
Java converte la stringa in numero intero
>
>
Python3
# Python implementation of Binary Indexed Tree> > # Returns sum of arr[0..index]. This function assumes> # that the array is preprocessed and partial sums of> # array elements are stored in BITree[].> def> getsum(BITTree,i):> >s>=> 0> #initialize result> > ># index in BITree[] is 1 more than the index in arr[]> >i>=> i>+>1> > ># Traverse ancestors of BITree[index]> >while> i>>0>:> > ># Add current element of BITree to sum> >s>+>=> BITTree[i]> > ># Move index to parent node in getSum View> >i>->=> i & (>->i)> >return> s> > # Updates a node in Binary Index Tree (BITree) at given index> # in BITree. The given value 'val' is added to BITree[i] and> # all of its ancestors in tree.> def> updatebit(BITTree , n , i ,v):> > ># index in BITree[] is 1 more than the index in arr[]> >i>+>=> 1> > ># Traverse all ancestors and add 'val'> >while> i <>=> n:> > ># Add 'val' to current node of BI Tree> >BITTree[i]>+>=> v> > ># Update index to that of parent in update View> >i>+>=> i & (>->i)> > > # Constructs and returns a Binary Indexed Tree for given> # array of size n.> def> construct(arr, n):> > ># Create and initialize BITree[] as 0> >BITTree>=> [>0>]>*>(n>+>1>)> > ># Store the actual values in BITree[] using update()> >for> i>in> range>(n):> >updatebit(BITTree, n, i, arr[i])> > ># Uncomment below lines to see contents of BITree[]> >#for i in range(1,n+1):> ># print BITTree[i],> >return> BITTree> > > # Driver code to test above methods> freq>=> [>2>,>1>,>1>,>3>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]> BITTree>=> construct(freq,>len>(freq))> print>(>'Sum of elements in arr[0..5] is '> +> str>(getsum(BITTree,>5>)))> freq[>3>]>+>=> 6> updatebit(BITTree,>len>(freq),>3>,>6>)> print>(>'Sum of elements in arr[0..5]'>+> >' after update is '> +> str>(getsum(BITTree,>5>)))> > # This code is contributed by Raju Varshney> |
>
>
conversione del tipo e casting in Java
C#
// C# program to demonstrate lazy> // propagation in segment tree> using> System;> > public> class> BinaryIndexedTree> {> >// Max tree size> >readonly> static> int> MAX = 1000;> > >static> int> []BITree =>new> int>[MAX];> > >/* n -->N. di elementi presenti nell'array di input.> >BITree[0..n] -->Matrice che rappresenta Binary> >Indexed Tree.> >arr[0..n-1] -->Array di input per il quale prefisso somma> >is evaluated. */> > >// Returns sum of arr[0..index]. This function> >// assumes that the array is preprocessed and> >// partial sums of array elements are stored> >// in BITree[].> >int> getSum(>int> index)> >{> >int> sum = 0;>// Initialize result> > >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index + 1;> > >// Traverse ancestors of BITree[index]> >while>(index>0)> >{> >// Add current element of BITree> >// to sum> >sum += BITree[index];> > >// Move index to parent node in> >// getSum View> >index -= index & (-index);> >}> >return> sum;> >}> > >// Updates a node in Binary Index Tree (BITree)> >// at given index in BITree. The given value> >// 'val' is added to BITree[i] and all of> >// its ancestors in tree.> >public> static> void> updateBIT(>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 BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> >}> > >/* Function to construct fenwick tree> >from given array.*/> >void> constructBITree(>int> []arr,>int> n)> >{> >// Initialize BITree[] as 0> >for>(>int> i = 1; i <= n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[]> >// using update()> >for>(>int> i = 0; i updateBIT(n, i, arr[i]); } // Driver code public static void Main(String []args) { int []freq = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = freq.Length; BinaryIndexedTree tree = new BinaryIndexedTree(); // Build fenwick tree from given array tree.constructBITree(freq, n); Console.WriteLine('Sum of elements in arr[0..5]'+ ' is '+ tree.getSum(5)); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated Console.WriteLine('Sum of elements in arr[0..5]'+ ' after update is ' + tree.getSum(5)); } } // This code is contributed by PrinciRaj1992> |
>
>
Javascript
tutorial sul selenio java
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->N. di elementi presenti nell'array di input.> >BITree[0..n] -->Matrice che rappresenta Binary> >Indexed Tree.> >arr[0..n-1] -->Array di input per il quale prefisso somma> >is evaluated. */> > >// Returns sum of arr[0..index]. This function> >// assumes that the array is preprocessed and> >// partial sums of array elements are stored> >// in BITree[].> function> getSum( index)> {> >let sum = 0;>// Initialize result> > >// index in BITree[] is 1 more than> >// the index in arr[]> >index = index + 1;> > >// Traverse ancestors of BITree[index]> >while>(index>0)> >{> >// Add current element of BITree> >// to sum> >sum += BITree[index];> > >// Move index to parent node in> >// getSum View> >index -= index & (-index);> >}> >return> sum;> }> > // Updates a node in Binary Index Tree (BITree)> >// at given index in BITree. The given value> >// 'val' is added to BITree[i] and all of> >// its ancestors in tree.> function> updateBIT(n,index,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 BIT Tree> >BITree[index] += val;> > >// Update index to that of parent> >// in update View> >index += index & (-index);> >}> }> > /* Function to construct fenwick tree> >from given array.*/> function> constructBITree(arr,n)> {> >// Initialize BITree[] as 0> >for>(let i=1; i<=n; i++)> >BITree[i] = 0;> > >// Store the actual values in BITree[]> >// using update()> >for>(let i = 0; i updateBIT(n, i, arr[i]); } // Main function let freq=[2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]; let n = freq.length; // Build fenwick tree from given array constructBITree(freq, n); document.write('Sum of elements in arr[0..5]'+ ' is '+ getSum(5)+' '); // Let use test the update operation freq[3] += 6; // Update BIT for above change in arr[] updateBIT(n, 3, 6); // Find sum after the value is updated document.write('Sum of elements in arr[0..5]'+ ' after update is ' + getSum(5)); // This code is contributed by patel2127> |
>
>Produzione
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Complessità temporale: O(NLogN)
Spazio ausiliario: SU)
Possiamo estendere l'albero indicizzato binario per calcolare la somma di un intervallo in tempo O (Logn)?
SÌ. rangeSum(l, r) = getSum(r) – getSum(l-1).
Applicazioni:
L'implementazione dell'algoritmo di codifica aritmetica. Lo sviluppo dell'albero indicizzato binario è stato motivato principalmente dalla sua applicazione in questo caso. Vedere Questo per ulteriori dettagli.
Problemi di esempio:
Contare le inversioni in un array | Imposta 3 (utilizzando BIT)
Albero indicizzato binario bidimensionale o albero di Fenwick
Contare i triangoli in uno spazio rettangolare usando BIT
Riferimenti:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees