Tarkastellaan seuraavaa ongelmaa ymmärtääksemme binaariindeksin puun.
Meillä on taulukko arr[0 . . . n-1]. Haluaisimme
1 Laske ensimmäisten i-alkioiden summa.
2 Muokkaa taulukon tietyn elementin arvoa arr[i] = x missä 0 <= i <= n-1.
A yksinkertainen ratkaisu on ajaa silmukka 0:sta i-1:een ja laskea elementtien summa. Päivitä arvo tekemällä arr[i] = x. Ensimmäinen operaatio kestää O(n) aikaa ja toinen operaatio O(1) aikaa. Toinen yksinkertainen ratkaisu on luoda ylimääräinen taulukko ja tallentaa ensimmäisten i. elementtien summa i:nnen indeksin kohdalle tähän uuteen taulukkoon. Tietyn alueen summa voidaan nyt laskea O(1) ajassa, mutta päivitys kestää nyt O(n) aikaa. Tämä toimii hyvin, jos kyselytoimintoja on paljon, mutta päivitystoimintoja on hyvin vähän.
Voisimmeko suorittaa sekä kyselyn että päivitystoiminnot O(log n) -ajassa?
Yksi tehokas ratkaisu on käyttää segmenttipuuta, joka suorittaa molemmat toiminnot O(logn)-ajassa.
Vaihtoehtoinen ratkaisu on Binary Indexed Tree, joka saavuttaa myös O(Logn)-ajan monimutkaisuuden molemmille operaatioille. Segmenttipuuhun verrattuna binaarinen indeksoitu puu vaatii vähemmän tilaa ja on helpompi toteuttaa. .
Edustus
Binääri-indeksoitu puu esitetään taulukona. Olkoon taulukko BITree[]. Jokainen binaari-indeksoidun puun solmu tallentaa joidenkin syöttötaulukon elementtien summan. Binaariindeksoidun puun koko on yhtä suuri kuin syöttötaulukon koko, joka on merkitty n:llä. Alla olevassa koodissa käytämme kokoa n+1 käyttöönoton helpottamiseksi.
Rakentaminen
Alustamme kaikki BITree[]:n arvot nollaksi. Sitten kutsumme update():tä kaikille indekseille, update()-toimintoa käsitellään alla.
Toiminnot
getSum(x): Palauttaa alitaulukon arr[0,…,x] summan
// Palauttaa alitaulukon arr[0,…,x] summan käyttämällä BITree[0..n]:a, joka on muodostettu arr[0..n-1]:stä
1) Alusta lähtösumma 0:ksi, nykyinen indeksi x+1.
2) Suorita seuraava, kun nykyinen indeksi on suurempi kuin 0.
…a) Lisää BITree[index] summaan
…b) Siirry BITree[index]:n yläpäähän. Vanhemman saa pois poistamalla
viimeinen asetettu bitti nykyisestä indeksistä, eli indeksi = indeksi – (indeksi & (-indeksi))
3) Palautussumma.
Yllä oleva kaavio tarjoaa esimerkin siitä, kuinka getSum() toimii. Tässä muutamia tärkeitä havaintoja.
BITree[0] on valesolmu.
BITree[y] on BITree[x]:n emo, jos ja vain jos y voidaan saada poistamalla viimeinen asetettu bitti x:n binääriesityksestä, eli y = x – (x & (-x)).
Solmun BITree[y] lapsisolmu BITree[x] tallentaa alkioiden summan välillä y(sisältää) ja x(ei sisällä): arr[y,…,x).
update(x, val): Päivittää binaarisen indeksoidun puun (BIT) suorittamalla arr[index] += val
// Huomaa, että update(x, val) -toiminto ei muuta arr[]. Se tekee muutoksia vain BITreeen[]
1) Alusta nykyinen indeksi muodossa x+1.
2) Toimi seuraavasti, kun nykyinen indeksi on pienempi tai yhtä suuri kuin n.
…a) Lisää val BITreeen[index]
…b) Siirry BITree[index]:n seuraavaan elementtiin. Seuraava elementti voidaan saada lisäämällä nykyisen indeksin viimeistä asetettua bittiä, eli indeksi = indeksi + (indeksi & (-indeksi))
Päivitystoiminnon on varmistettava, että kaikki BITree-solmut, jotka sisältävät arr[i]:n alueellaan, päivitetään. Kierrämme tällaisten solmujen yli BITreessä lisäämällä toistuvasti desimaaliluvun, joka vastaa nykyisen indeksin viimeistä asetettua bittiä.
Kuinka binaariindeksoitu puu toimii?
Idea perustuu siihen, että kaikki positiiviset kokonaisluvut voidaan esittää 2:n potenssien summana. Esimerkiksi 19 voidaan esittää muodossa 16 + 2 + 1. Jokainen BITreen solmu tallentaa n elementin summan, jossa n on a potenssi 2. Esimerkiksi yllä olevassa ensimmäisessä kaaviossa (getSum()-kaavio) 12 ensimmäisen elementin summa voidaan saada neljän viimeisen alkion summalla (9 - 12) plus 8:n summa elementtejä (1-8). Joukkobittien lukumäärä luvun n binääriesityksessä on O(Logn). Siksi käytämme korkeintaan O(Logn)-solmuja sekä getSum()- että update()-operaatioissa. Rakenteen aikamonimutkaisuus on O(nLogn), koska se kutsuu update() kaikille n elementille.
Toteutus:
Seuraavat ovat Binary Indexed Treen toteutukset.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Syötetaulukossa olevien elementtien lukumäärä.>> > // 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 esimerkki
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 -->Syötetaulukossa olevien elementtien lukumäärä.>> >Indexed Tree.> >arr[0..n-1] -->Syötetaulukko, jonka etuliitteen summa> >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> |
>
>
Python 3
# 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#
keskipainike css
// 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 -->Syötetaulukossa olevien elementtien lukumäärä.>> >Indexed Tree.> >arr[0..n-1] -->Syötetaulukko, jonka etuliitteen summa> >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 -->Syötetaulukossa olevien elementtien lukumäärä.>> >Indexed Tree.> >arr[0..n-1] -->Syötetaulukko, jonka etuliitteen summa> >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> |
>
>Lähtö
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Aika monimutkaisuus: O(NLogN)
Aputila: PÄÄLLÄ)
Voimmeko laajentaa binaari-indeksipuuta alueen summan laskemiseen O(logn)-ajassa?
Joo. rangeSum(l, r) = getSum(r) – getSum(l-1).
Sovellukset:
Aritmeettisen koodausalgoritmin toteutus. Binääriindeksipuun kehittäminen johtui ensisijaisesti sen soveltamisesta tässä tapauksessa. Katso Tämä Lisätietoja.
Esimerkkiongelmat:
Laske inversiot taulukossa | Sarja 3 (käyttäen BIT:tä)
Kaksiulotteinen binaarinen indeksoitu puu tai Fenwick-puu
Kolmioiden laskeminen suorakaiteen muotoisessa avaruudessa BIT:n avulla
Viitteet:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees