Să luăm în considerare următoarea problemă pentru a înțelege Arborele indexat binar.
Avem o matrice arr[0 . . . n-1]. Am dori să
1 Calculați suma primelor i elemente.
2 Modificați valoarea unui element specificat al matricei arr[i] = x unde 0 <= i <= n-1.
A solutie simpla este să rulezi o buclă de la 0 la i-1 și să calculezi suma elementelor. Pentru a actualiza o valoare, faceți pur și simplu arr[i] = x. Prima operație durează timp O(n), iar a doua operație durează timp O(1). O altă soluție simplă este de a crea o matrice suplimentară și de a stoca suma primului i-lea elemente la i-lea index în această nouă matrice. Suma unui interval dat poate fi acum calculată în timp O(1), dar operația de actualizare durează acum O(n) timp. Acest lucru funcționează bine dacă există un număr mare de operațiuni de interogare, dar un număr foarte mic de operațiuni de actualizare.
Am putea efectua atât operațiile de interogare, cât și de actualizare în timp O(log n)?
O soluție eficientă este utilizarea Segment Tree care efectuează ambele operații în timp O(Logn).
O soluție alternativă este Binary Indexed Tree, care realizează și complexitatea timpului O(Logn) pentru ambele operațiuni. În comparație cu Segment Tree, Binary Indexed Tree necesită mai puțin spațiu și este mai ușor de implementat. .
Reprezentare
Arborele binar indexat este reprezentat ca o matrice. Lasă matricea să fie BITree[]. Fiecare nod al Arborelui Binar Indexat stochează suma unor elemente din tabloul de intrare. Mărimea arborelui indexat binar este egală cu dimensiunea matricei de intrare, notat cu n. În codul de mai jos, folosim o dimensiune de n+1 pentru ușurința implementării.
Constructie
Inițializam toate valorile din BITree[] ca 0. Apoi apelăm update() pentru toți indecșii, operațiunea update() este discutată mai jos.
Operațiuni
getSum(x): returnează suma sub-matricei arr[0,…,x]
// Returnează suma sub-matricei arr[0,…,x] folosind BITree[0..n], care este construit din arr[0..n-1]
1) Inițializați suma de ieșire ca 0, indicele curent ca x+1.
2) Urmăriți în timp ce indicele curent este mai mare decât 0.
…a) Adăugați BITree[index] la sumă
…b) Accesați părintele BITree[index]. Părintele poate fi obținut prin eliminare
ultimul bit setat din indexul curent, adică index = index – (index & (-index))
3) Suma returnată.
Diagrama de mai sus oferă un exemplu despre cum funcționează getSum(). Iată câteva observații importante.
BITree[0] este un nod inactiv.
BITree[y] este părintele lui BITree[x], dacă și numai dacă y poate fi obținut prin eliminarea ultimului bit setat din reprezentarea binară a lui x, adică y = x – (x & (-x)).
Nodul copil BITree[x] al nodului BITree[y] stochează suma elementelor dintre y(inclusiv) și x(exclusiv): arr[y,…,x).
update(x, val): actualizează arborele indexat binar (BIT) prin efectuarea arr[index] += val
// Rețineți că operația de actualizare (x, val) nu se va schimba arr[]. Face doar modificări în BITree[]
1) Inițializați indexul curent ca x+1.
2) Faceți următoarele în timp ce indicele curent este mai mic sau egal cu n.
…a) Adăugați val la BITree[index]
…b) Mergeți la următorul element al BITree[index]. Următorul element poate fi obținut prin creșterea ultimului bit setat al indexului curent, adică index = index + (index & (-index))
Funcția de actualizare trebuie să se asigure că toate nodurile BITree care conțin arr[i] în intervalele lor sunt actualizate. Facem bucla peste astfel de noduri din BITree adăugând în mod repetat numărul zecimal corespunzător ultimului bit setat al indexului curent.
Cum funcționează arborele indexat binar?
Ideea se bazează pe faptul că toate numerele întregi pozitive pot fi reprezentate ca sumă a puterilor lui 2. De exemplu 19 poate fi reprezentat ca 16 + 2 + 1. Fiecare nod al BITree stochează suma n elemente unde n este un puterea lui 2. De exemplu, în prima diagramă de mai sus (diagrama pentru getSum()), suma primelor 12 elemente poate fi obținută prin suma ultimelor 4 elemente (de la 9 la 12) plus suma lui 8 elemente (de la 1 la 8). Numărul de biți setați în reprezentarea binară a unui număr n este O(Logn). Prin urmare, traversăm cel mult nodurile O(Logn) atât în operațiile getSum() cât și în operațiunile update(). Complexitatea de timp a construcției este O(nLogn), deoarece apelează update() pentru toate cele n elemente.
Implementare:
Următoarele sunt implementările lui Binary Indexed Tree.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Nr. elemente prezente în tabloul de intrare.>>> > // 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; }> |
>
>
Java
vârsta pete davidson
// 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 -->Nr. elemente prezente în tabloul de intrare.>>> >Indexed Tree.> >arr[0..n-1] -->Matrice de intrare pentru care suma prefixului> >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>>>> >{> >// 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ște șirul în întreg
>
>
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>>>> > ># 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> |
>
>
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 -->Numărul de elemente prezente în tabloul de intrare.>>> >Indexed Tree.> >arr[0..n-1] -->Matrice de intrare pentru care suma prefixului> >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
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Nr. elemente prezente în tabloul de intrare.>>> >Indexed Tree.> >arr[0..n-1] -->Matrice de intrare pentru care suma prefixului> >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> |
>
>Ieșire
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Complexitatea timpului: O(NLogN)
Spațiu auxiliar: PE)
conversie de tip și turnare în java
Putem extinde arborele indexat binar pentru a calcula suma unui interval în timp O(Logn)?
Da. rangeSum(l, r) = getSum(r) – getSum(l-1).
Aplicatii:
Implementarea algoritmului de codare aritmetică. Dezvoltarea arborelui indexat binar a fost motivată în primul rând de aplicarea lui în acest caz. Vedea acest pentru mai multe detalii.
Exemple de probleme:
Numărați inversiunile într-o matrice | Setul 3 (folosind BIT)
Arborele binar bidimensional indexat sau arborele Fenwick
Numărarea triunghiurilor într-un spațiu dreptunghiular folosind BIT
Referinte:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees