Pozrime sa na nasledujúci problém, aby sme pochopili binárny indexovaný strom.
Máme pole arr[0 . . . n-1]. Radi by sme
1 Vypočítajte súčet prvých i prvkov.
2 Upravte hodnotu zadaného prvku poľa arr[i] = x kde 0 <= i <= n-1.
A jednoduché riešenie je spustiť cyklus od 0 do i-1 a vypočítať súčet prvkov. Ak chcete aktualizovať hodnotu, jednoducho urobte arr[i] = x. Prvá operácia trvá O(n) čas a druhá operácia O(1) čas. Ďalším jednoduchým riešením je vytvoriť ďalšie pole a uložiť súčet prvých i-tých prvkov na i-tom indexe v tomto novom poli. Súčet daného rozsahu sa teraz môže vypočítať v čase O(1), ale operácia aktualizácie teraz trvá O(n) čas. Funguje to dobre, ak existuje veľký počet operácií dotazu, ale veľmi málo operácií aktualizácie.
Mohli by sme vykonať operácie dotazu aj aktualizácie v čase O (log n)?
Jedným z efektívnych riešení je použitie Segment Tree, ktorý vykonáva obe operácie v čase O(Logn).
Alternatívnym riešením je Binary Indexed Tree, ktorý tiež dosahuje časovú zložitosť O(Logn) pre obe operácie. V porovnaní so Segmentovým stromom vyžaduje binárny indexovaný strom menej miesta a je jednoduchšie implementovať. .
zastupovanie
Binárny indexovaný strom je reprezentovaný ako pole. Nech je pole BITree[]. Každý uzol binárneho indexovaného stromu ukladá súčet niektorých prvkov vstupného poľa. Veľkosť binárneho indexovaného stromu sa rovná veľkosti vstupného poľa, označeného ako n. V nižšie uvedenom kóde používame veľkosť n+1 pre ľahkú implementáciu.
Stavebníctvo
Inicializujeme všetky hodnoty v BITree[] ako 0. Potom zavoláme update() pre všetky indexy, operácia update() je popísaná nižšie.
Operácie
getSum(x): Vráti súčet podpola arr[0,…,x]
// Vráti súčet podpola arr[0,…,x] pomocou BITree[0..n], ktorý je vytvorený z arr[0..n-1]
1) Inicializujte výstupný súčet ako 0, aktuálny index ako x+1.
2) Postupujte, kým je aktuálny index väčší ako 0.
…a) Pridajte BITree[index] k súčtu
…b) Prejdite na nadradenú stránku BITree[index]. Rodič možno získať odstránením
posledný nastavený bit z aktuálneho indexu, t.j. index = index – (index & (-index))
3) Vrátená suma.
Vyššie uvedený diagram poskytuje príklad, ako funguje getSum(). Tu je niekoľko dôležitých postrehov.
BITree[0] je fiktívny uzol.
BITree[y] je rodičom BITree[x] vtedy a len vtedy, ak y možno získať odstránením posledného nastaveného bitu z binárnej reprezentácie x, teda y = x – (x & (-x)).
Podradený uzol BITree[x] uzla BITree[y] uchováva súčet prvkov medzi y(vrátane) a x(výhradne): arr[y,…,x).
update(x, val): Aktualizuje binárny indexovaný strom (BIT) vykonaním arr[index] += val
// Všimnite si, že operácia update(x, val) nezmení arr[]. Vykonáva iba zmeny v BITree[]
1) Inicializujte aktuálny index ako x+1.
2) Keď je aktuálny index menší alebo rovný n, urobte nasledovné.
…a) Pridajte hodnotu do BITree[index]
…b) Prejdite na ďalší prvok BITree[index]. Ďalší prvok možno získať zvýšením posledného nastaveného bitu aktuálneho indexu, t.j. index = index + (index & (-index))
Funkcia aktualizácie sa musí uistiť, že sa aktualizujú všetky uzly BITree, ktoré obsahujú arr[i] v rámci svojich rozsahov. Prechádzame cez takéto uzly v BITree opakovaným pridávaním desatinného čísla zodpovedajúceho poslednému nastavenému bitu aktuálneho indexu.
Ako funguje binárny indexovaný strom?
Myšlienka je založená na skutočnosti, že všetky kladné celé čísla môžu byť reprezentované ako súčet mocnin 2. Napríklad 19 môže byť reprezentované ako 16 + 2 + 1. Každý uzol BITree ukladá súčet n prvkov, kde n je a mocnina 2. Napríklad v prvom diagrame vyššie (diagram pre getSum()) možno súčet prvých 12 prvkov získať súčtom posledných 4 prvkov (od 9 do 12) plus súčet 8 prvky (od 1 do 8). Počet nastavených bitov v binárnej reprezentácii čísla n je O(Logn). Preto prechádzame najviac O(Logn) uzlami v operáciách getSum() aj update(). Časová zložitosť konštrukcie je O(nLogn), pretože volá update() pre všetkých n prvkov.
Implementácia:
Nasledujú implementácie binárneho indexovaného stromu.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Počet prvkov prítomných vo vstupnom poli.> >BITree[0..n] -->Pole, ktoré predstavuje binárny indexovaný strom.> >arr[0..n-1] -->Vstupné pole, pre ktoré sa vyhodnocuje súčet prefixov. */> > // 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; }> |
premenná 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 -->Počet prvkov prítomných vo vstupnom poli.> >BITree[0..n] -->Pole, ktoré predstavuje binárne> >Indexed Tree.> >arr[0..n-1] -->Vstupné pole, ktorého súčet predpony> >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#
zoznam programov python
// 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 -->Počet prvkov prítomných vo vstupnom poli.> >BITree[0..n] -->Pole, ktoré predstavuje binárne> >Indexed Tree.> >arr[0..n-1] -->Vstupné pole, ktorého súčet predpony> >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> |
porovnať s reťazcom
>
>
Javascript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Počet prvkov prítomných vo vstupnom poli.> >BITree[0..n] -->Pole, ktoré predstavuje binárne> >Indexed Tree.> >arr[0..n-1] -->Vstupné pole, ktorého súčet predpony> >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> |
>
>Výkon
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Časová zložitosť: O(NLogN)
Pomocný priestor: O(N)
Môžeme rozšíriť binárny indexovaný strom na výpočet súčtu rozsahu v čase O(Logn)?
Áno. rangeSum(l, r) = getSum(r) – getSum(l-1).
Aplikácie:
Implementácia aritmetického kódovacieho algoritmu. Vývoj Binary Indexed Tree bol v tomto prípade primárne motivovaný jeho aplikáciou. Pozri toto pre viac detailov.
Príklady problémov:
Počítajte inverzie v poli | Sada 3 (pomocou BIT)
Dvojrozmerný binárny indexovaný strom alebo Fenwickov strom
Počítanie trojuholníkov v obdĺžnikovom priestore pomocou BIT
Referencie:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees