Razmislimo o naslednji težavi, da bi razumeli binarno indeksirano drevo.
Imamo matriko arr[0. . . n-1]. Želeli bi
1 Izračunajte vsoto prvih i elementov.
2 Spremenite vrednost določenega elementa matrike arr[i] = x, kjer je 0 <= i <= n-1.
A preprosta rešitev je zagnati zanko od 0 do i-1 in izračunati vsoto elementov. Če želite posodobiti vrednost, preprosto naredite arr[i] = x. Prva operacija traja O(n) časa, druga pa O(1) časa. Druga preprosta rešitev je ustvariti dodatno matriko in shraniti vsoto prvih i-tih elementov pri i-tem indeksu v tej novi matriki. Vsoto danega obsega je zdaj mogoče izračunati v O(1) času, vendar operacija posodobitve zdaj traja O(n) časa. To dobro deluje, če obstaja veliko število operacij poizvedbe, vendar zelo malo operacij posodabljanja.
Ali lahko izvedemo operacijo poizvedbe in posodobitve v O(log n) času?
Ena od učinkovitih rešitev je uporaba Segment Tree, ki izvede obe operaciji v O(Logn) času.
Alternativna rešitev je binarno indeksirano drevo, ki prav tako doseže časovno kompleksnost O(Logn) za obe operaciji. V primerjavi s segmentnim drevesom binarno indeksirano drevo zahteva manj prostora in ga je lažje implementirati. .
Zastopanje
Binarno indeksirano drevo je predstavljeno kot polje. Naj bo matrika BITree[]. Vsako vozlišče binarnega indeksiranega drevesa shrani vsoto nekaterih elementov vhodne matrike. Velikost binarnega indeksiranega drevesa je enaka velikosti vhodne matrike, označene z n. V spodnji kodi uporabljamo velikost n+1 za lažjo implementacijo.
Gradnja
Vse vrednosti v BITree[] inicializiramo kot 0. Nato pokličemo update() za vse indekse, operacija update() je obravnavana spodaj.
Operacije
getSum(x): Vrne vsoto podmatrike arr[0,…,x]
// Vrne vsoto podmatrike arr[0,…,x] z uporabo BITree[0..n], ki je sestavljena iz arr[0..n-1]
1) Inicializirajte izhodno vsoto kot 0, trenutni indeks kot x+1.
2) Naredite naslednje, medtem ko je trenutni indeks večji od 0.
…a) Vsoti dodajte BITree[index].
…b) Pojdite na nadrejenega elementa BITree[index]. Starša lahko pridobite z odstranitvijo
zadnji nastavljeni bit iz trenutnega indeksa, tj. indeks = indeks – (indeks & (-indeks))
3) Povratna vsota.
Zgornji diagram prikazuje primer delovanja getSum(). Tukaj je nekaj pomembnih opažanj.
BITree[0] je navidezno vozlišče.
BITree[y] je nadrejeni element BITree[x], če in samo če je y mogoče dobiti z odstranitvijo zadnjega nastavljenega bita iz binarne predstavitve x, to je y = x – (x & (-x)).
Podrejeno vozlišče BITree[x] vozlišča BITree[y] shrani vsoto elementov med y(vključno) in x(izključno): arr[y,…,x).
update(x, val): posodobi binarno indeksirano drevo (BIT) z izvedbo arr[index] += val
// Upoštevajte, da operacija update(x, val) ne bo spremenila arr[]. Spreminja samo BITree[]
1) Inicializirajte trenutni indeks kot x+1.
2) Naredite naslednje, medtem ko je trenutni indeks manjši ali enak n.
…a) Dodajte val v BITree[index]
…b) Pojdite na naslednji element BITree[index]. Naslednji element lahko dobite s povečanjem zadnjega nastavljenega bita trenutnega indeksa, tj. indeks = indeks + (indeks & (-indeks))
Funkcija posodabljanja mora zagotoviti, da se posodobijo vsa vozlišča BITree, ki vsebujejo arr[i] v svojih obsegih. Takšna vozlišča v BITreeju preletimo tako, da večkrat dodamo decimalno število, ki ustreza zadnjemu nastavljenemu bitu trenutnega indeksa.
Kako deluje binarno indeksirano drevo?
Ideja temelji na dejstvu, da je mogoče vsa pozitivna cela števila predstaviti kot vsoto potenc števila 2. Na primer, 19 je mogoče predstaviti kot 16 + 2 + 1. Vsako vozlišče drevesa BITree shrani vsoto n elementov, kjer je n a potenco 2. Na primer, v prvem zgornjem diagramu (diagram za getSum()) lahko vsoto prvih 12 elementov dobimo z vsoto zadnjih 4 elementov (od 9 do 12) plus vsoto 8 elementov (od 1 do 8). Število nastavljenih bitov v binarni predstavitvi števila n je O(Logn). Zato prečkamo največ O(Logn) vozlišč v obeh operacijah getSum() in update(). Časovna zapletenost konstrukcije je O(nLogn), saj kliče update() za vseh n elementov.
Izvedba:
Sledijo izvedbe binarnega indeksiranega drevesa.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Število elementov v vhodnem polju.> >BITree[0..n] -->Matrika, ki predstavlja binarno indeksirano drevo.> >arr[0..n-1] -->Vhodna matrika, za katero je ovrednotena vsota predpone. */> > // 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; }> |
>
>
arraylist razvrščena java
Java
// 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 -->Število elementov v vhodnem polju.> >BITree[0..n] -->Matrika, ki predstavlja dvojiško>>> >arr[0..n-1] -->Vnosna matrika, za katero predpono vsota> >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> |
>
>
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> |
>
>
C#
'primov algoritem'
// 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 -->Število elementov v vhodnem polju.> >BITree[0..n] -->Matrika, ki predstavlja dvojiško>> >Indexed Tree.> >arr[0..n-1] -->Vnosna matrika, za katero vsoto predpone> >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 -->Število elementov v vhodnem polju.> >BITree[0..n] -->Matrika, ki predstavlja dvojiško>> >Indexed Tree.> >arr[0..n-1] -->Vnosna matrika, za katero predpono vsota> >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> |
>
>Izhod
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Časovna zapletenost: O(NLogN)
Pomožni prostor: O(N)
Ali lahko razširimo binarno indeksirano drevo na izračun vsote obsega v O(Logn) času?
ja obsegSum(l, r) = getSum(r) – getSum(l-1).
Aplikacije:
Izvedba algoritma aritmetičnega kodiranja. Razvoj binarnega indeksiranega drevesa je bil v prvi vrsti motiviran z njegovo uporabo v tem primeru. glej to za več podrobnosti.
Primeri težav:
Preštej inverzije v matriki | 3. niz (z uporabo BIT)
Dvodimenzionalno binarno indeksirano drevo ali Fenwickovo drevo
Štetje trikotnikov v pravokotnem prostoru z BIT
Reference:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees