Podívejme se na následující problém, abychom pochopili binární indexovaný strom.
Máme pole arr[0 . . . n-1]. Rádi bychom
1 Vypočítejte součet prvních i prvků.
2 Upravte hodnotu zadaného prvku pole arr[i] = x kde 0 <= i <= n-1.
A jednoduché řešení je spustit smyčku od 0 do i-1 a vypočítat součet prvků. Chcete-li aktualizovat hodnotu, jednoduše proveďte arr[i] = x. První operace trvá O(n) čas a druhá operace trvá O(1) čas. Dalším jednoduchým řešením je vytvořit další pole a uložit součet prvních i-tých prvků na i-tém indexu do tohoto nového pole. Součet daného rozsahu lze nyní vypočítat v čase O(1), ale operace aktualizace nyní trvá O(n) čas. To funguje dobře, pokud existuje velký počet operací dotazů, ale velmi málo operací aktualizace.
Mohli bychom provádět operace dotazu i aktualizace v čase O(log n)?
Jedním z efektivních řešení je použití stromu segmentů, který provádí obě operace v čase O(Logn).
Alternativním řešením je Binary Indexed Tree, který také dosahuje časové složitosti O(Logn) pro obě operace. Ve srovnání se Segmentovým stromem vyžaduje binární indexovaný strom méně místa a snáze se implementuje. .
Reprezentace
Binární indexovaný strom je reprezentován jako pole. Nechť pole je BITree[]. Každý uzel Binary Indexed Tree ukládá součet některých prvků vstupního pole. Velikost binárního indexovaného stromu je rovna velikosti vstupního pole, označeného jako n. V níže uvedeném kódu používáme velikost n+1 pro snadnou implementaci.
Konstrukce
Inicializujeme všechny hodnoty v BITree[] jako 0. Poté zavoláme update() pro všechny indexy, operace update() je popsána níže.
Operace
getSum(x): Vrací součet dílčího pole arr[0,…,x]
// Vrátí součet dílčího pole arr[0,…,x] pomocí BITree[0..n], který je vytvořen z arr[0..n-1]
1) Inicializujte výstupní součet na 0, aktuální index na x+1.
2) Postupujte, dokud je aktuální index větší než 0.
…a) Přidejte BITree[index] k součtu
…b) Přejděte na nadřazenou položku BITree[index]. Rodič lze získat odebráním
poslední nastavený bit z aktuálního indexu, tj. index = index – (index & (-index))
3) Vrácená částka.
Výše uvedený diagram poskytuje příklad toho, jak getSum() funguje. Zde je několik důležitých postřehů.
BITree[0] je fiktivní uzel.
BITree[y] je rodič BITree[x], právě tehdy, když y lze získat odstraněním posledního nastaveného bitu z binární reprezentace x, tedy y = x – (x & (-x)).
Podřízený uzel BITree[x] uzlu BITree[y] ukládá součet prvků mezi y(včetně) a x(exkluzivní): arr[y,…,x).
update(x, val): Aktualizuje binární indexovaný strom (BIT) provedením arr[index] += val
// Všimněte si, že operace update(x, val) nezmění arr[]. Provádí pouze změny v BITree[]
1) Inicializujte aktuální index jako x+1.
2) Proveďte následující, dokud je aktuální index menší nebo roven n.
…a) Přidejte hodnotu do BITree[index]
…b) Přejít na další prvek BITree[index]. Další prvek lze získat inkrementací posledního nastaveného bitu aktuálního indexu, tj. index = index + (index & (-index))
typy sítí
Funkce aktualizace musí zajistit, aby byly aktualizovány všechny uzly BITree, které obsahují arr[i] v rámci svých rozsahů. Přes takové uzly v BITree procházíme opakovaným přidáváním desetinného čísla odpovídajícímu poslednímu nastavenému bitu aktuálního indexu.
Jak funguje binární indexovaný strom?
Myšlenka je založena na skutečnosti, že všechna kladná celá čísla mohou být reprezentována jako součet mocnin 2. Například 19 může být reprezentováno jako 16 + 2 + 1. Každý uzel BITree ukládá součet n prvků, kde n je a mocnina 2. Například v prvním diagramu výše (diagram pro getSum()) lze součet prvních 12 prvků získat součtem posledních 4 prvků (od 9 do 12) plus součet 8 prvky (od 1 do 8). Počet nastavených bitů v binární reprezentaci čísla n je O(Logn). Proto procházíme maximálně O(Logn) uzly v operacích getSum() i update(). Časová složitost konstrukce je O(nLogn), protože volá update() pro všech n prvků.
Implementace:
Následují implementace binárního indexovaného stromu.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Počet prvků přítomných ve vstupním poli.> >BITree[0..n] -->Pole, které představuje binární indexovaný strom.> >arr[0..n-1] -->Vstupní pole, pro které je vyhodnocen součet prefixů. */> > // 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; }> |
>
>
Jáva
// 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 prvků přítomných ve vstupním poli.> >BITree[0..n] -->Pole, které představuje binární> >Indexed Tree.> >arr[0..n-1] -->Vstupní pole, jehož předpona součet> >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#
// 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 prvků přítomných ve vstupním poli.> >BITree[0..n] -->Pole, které představuje binární> >Indexed Tree.> >arr[0..n-1] -->Vstupní pole, jehož předpona součet> >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 -->Počet prvků přítomných ve vstupním poli.> >BITree[0..n] -->Pole, které představuje binární> >Indexed Tree.> >arr[0..n-1] -->Vstupní pole, jehož předpona součet> >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ýstup
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Časová náročnost: O(NLogN)
Pomocný prostor: NA)
Můžeme rozšířit binární indexovaný strom na výpočet součtu rozsahu v čase O(Logn)?
Ano. rangeSum(l, r) = getSum(r) – getSum(l-1).
Aplikace:
Implementace aritmetického kódovacího algoritmu. Vývoj Binary Indexed Tree byl v tomto případě motivován především jeho aplikací. Vidět tento Více podrobností.
Příklady problémů:
Počítejte inverze v poli | Sada 3 (pomocí BIT)
Dvourozměrný binární indexovaný strom nebo Fenwickův strom
Počítání trojúhelníků v obdélníkovém prostoru pomocí BIT
Reference:
http://cs.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees