Apskatīsim šādu problēmu, lai izprastu bināro indeksēto koku.
Mums ir masīvs arr[0 . . . n-1]. Mēs gribētu
1 Aprēķiniet pirmo i elementu summu.
2 Mainiet norādītā masīva elementa vērtību arr[i] = x, kur 0 <= i <= n-1.
A vienkāršs risinājums ir palaist cilpu no 0 līdz i-1 un aprēķināt elementu summu. Lai atjauninātu vērtību, vienkārši izpildiet arr[i] = x. Pirmā darbība aizņem O(n) laiku, bet otrā darbība aizņem O(1) laiku. Vēl viens vienkāršs risinājums ir izveidot papildu masīvu un saglabāt pirmo i-to elementu summu i-tajā indeksā šajā jaunajā masīvā. Dotā diapazona summu tagad var aprēķināt pēc O(1) laika, bet atjaunināšanas darbībai tagad ir vajadzīgs O(n) laiks. Tas darbojas labi, ja ir liels skaits vaicājumu darbību, bet ļoti maz atjaunināšanas darbību.
Vai mēs varētu veikt gan vaicājumu, gan atjaunināšanas darbības O(log n) laikā?
Viens efektīvs risinājums ir izmantot Segment Tree, kas veic abas darbības O (Logn) laikā.
Alternatīvs risinājums ir Binary Indexed Tree, kas arī nodrošina O(Logn) laika sarežģītību abām operācijām. Salīdzinot ar segmentu koku, binārajam indeksam ir nepieciešams mazāk vietas, un to ir vieglāk ieviest. .
Pārstāvība
Bināri indeksētais koks tiek attēlots kā masīvs. Ļaujiet masīvam būt BITree[]. Katrs binārā indeksētā koka mezgls saglabā dažu ievades masīva elementu summu. Binārā indeksētā koka izmērs ir vienāds ar ievades masīva lielumu, kas apzīmēts ar n. Tālāk esošajā kodā mēs izmantojam izmēru n+1, lai atvieglotu ieviešanu.
Būvniecība
Mēs inicializējam visas BITree[] vērtības kā 0. Pēc tam mēs izsaucam update() visiem indeksiem, darbība update() ir apskatīta tālāk.
Operācijas
getSum(x): atgriež apakšmasīva arr[0,…,x] summu.
// Atgriež apakšmasīva arr[0,…,x] summu, izmantojot BITree[0..n], kas ir konstruēta no arr[0..n-1]
1) Inicializējiet izejas summu kā 0, pašreizējo indeksu kā x+1.
2) Veiciet tālāk norādītās darbības, kamēr pašreizējais indekss ir lielāks par 0.
…a) Pievienojiet BITree[index] summai
…b) Dodieties uz BITree[index] vecāku. Vecāku var iegūt, noņemot
pēdējais iestatītais bits no pašreizējā indeksa, t.i., indekss = indekss – (indekss un (-indekss))
3) Atdeves summa.
Iepriekš redzamajā diagrammā ir sniegts getSum() darbības piemērs. Šeit ir daži svarīgi novērojumi.
BITree[0] ir fiktīvs mezgls.
BITree[y] ir BITree[x] vecāks, ja un tikai tad, ja y var iegūt, noņemot pēdējo iestatīto bitu no x binārā attēlojuma, tas ir, y = x – (x & (-x)).
Mezgla BITree[y] pakārtotais mezgls BITree[x] saglabā elementu summu starp y (ieskaitot) un x (izņemot): arr[y,…,x).
update(x, val): atjaunina bināro indeksēto koku (BIT), izpildot arr[index] += val
// Ņemiet vērā, ka atjaunināšanas(x, val) darbība nemainīs arr[]. Tas veic izmaiņas tikai BITree[]
1) Inicializējiet pašreizējo indeksu kā x+1.
2) Veiciet tālāk norādītās darbības, kamēr pašreizējais indekss ir mazāks vai vienāds ar n.
…a) Pievienojiet vērtību BITree[indekss]
…b) Pāriet uz nākamo BITree[index] elementu. Nākamo elementu var iegūt, palielinot pašreizējā indeksa pēdējo iestatīto bitu, t.i., indekss = indekss + (indekss un (-indekss))
Atjaunināšanas funkcijai ir jāpārliecinās, ka tiek atjaunināti visi BITree mezgli, kuru diapazonā ir arr[i]. Mēs veicam cilpu pār šādiem BITree mezgliem, atkārtoti pievienojot decimālo skaitli, kas atbilst pašreizējā indeksa pēdējam iestatītajam bitam.
Kā darbojas bināri indeksētais koks?
Ideja ir balstīta uz faktu, ka visus pozitīvos veselus skaitļus var attēlot kā 2 pakāpju summu. Piemēram, 19 var attēlot kā 16 + 2 + 1. Katrs BITree mezgls glabā n elementu summu, kur n ir a Piemēram, pirmajā diagrammā augstāk (diagrammā getSum()) pirmo 12 elementu summu var iegūt, summējot pēdējos 4 elementus (no 9 līdz 12) plus summu 8 elementi (no 1 līdz 8). Iestatīto bitu skaits skaitļa n binārajā attēlojumā ir O(Logn). Tāpēc mēs šķērsojam ne vairāk kā O(Logn) mezglus gan getSum(), gan update() operācijās. Konstrukcijas laika sarežģītība ir O(nLogn), jo tā izsauc update() visiem n elementiem.
Īstenošana:
Tālāk ir norādītas binārā indeksētā koka ieviešanas iespējas.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Ievades masīvā esošo elementu skaits.>> > // 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
java ja vēl
// 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 -->Ievades masīvā esošo elementu skaits.>> >Indexed Tree.> >arr[0..n-1] -->Ievades masīvs, kura prefiksa 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> |
>
>
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 -->Ievades masīvā esošo elementu skaits.>> >Indexed Tree.> >arr[0..n-1] -->Ievades masīvs, kura prefiksa 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> |
>
>
ymail
Javascript
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Ievades masīvā esošo elementu skaits.>> >Indexed Tree.> >arr[0..n-1] -->Ievades masīvs, kura prefiksa 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> |
>
>Izvade
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Laika sarežģītība: O(NLogN)
Palīgtelpa: O(N)
Vai mēs varam paplašināt bināro indeksēto koku, lai aprēķinātu diapazona summu O(Logn) laikā?
Jā. rangeSum(l, r) = getSum(r) – getSum(l-1).
Lietojumprogrammas:
Aritmētiskā kodēšanas algoritma realizācija. Binārā indeksētā koka izstrādi galvenokārt motivēja tā pielietojums šajā gadījumā. Skat šis lai iegūtu sīkāku informāciju.
Problēmu piemēri:
Skaitīt inversijas masīvā | 3. kopa (izmantojot BIT)
Divdimensiju bināri indeksēts koks vai Fenvika koks
Trīsstūru skaitīšana taisnstūrveida telpā, izmantojot BIT
Atsauces:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees