Panagrinėkime šią problemą, kad suprastume dvejetainį indeksuotą medį.
Turime masyvą arr[0 . . . n-1]. Mes norėtume
1 Apskaičiuokite pirmųjų i elementų sumą.
2 Pakeiskite nurodyto masyvo elemento reikšmę arr[i] = x, kur 0 <= i <= n-1.
A paprastas sprendimas yra paleisti kilpą nuo 0 iki i-1 ir apskaičiuoti elementų sumą. Norėdami atnaujinti reikšmę, tiesiog atlikite arr[i] = x. Pirmoji operacija trunka O (n) laiko, o antra operacija trunka O (1) laiko. Kitas paprastas sprendimas yra sukurti papildomą masyvą ir šiame naujame masyve išsaugoti pirmųjų i-ųjų elementų sumą i-ajame indekse. Nurodyto diapazono sumą dabar galima apskaičiuoti pagal O(1) laiką, tačiau atnaujinimo operacija dabar trunka O(n) laiko. Tai gerai veikia, jei yra daug užklausos operacijų, bet labai mažai atnaujinimo operacijų.
Ar galėtume atlikti ir užklausos, ir atnaujinimo operacijas per O(log n) laiką?
Vienas veiksmingų sprendimų yra naudoti segmentų medį, kuris atlieka abi operacijas per O (Prisijungimo) laiką.
Alternatyvus sprendimas yra Binary Indexed Tree, kuris taip pat pasiekia O (Logn) laiko sudėtingumą abiem operacijoms. Palyginti su Segment Tree, dvejetainis indeksuotas medis reikalauja mažiau vietos ir yra lengviau įgyvendinamas. .
Atstovavimas
Dvejetainis indeksuotas medis vaizduojamas kaip masyvas. Tegul masyvas yra BITree[]. Kiekvienas dvejetainio indeksuoto medžio mazgas saugo kai kurių įvesties masyvo elementų sumą. Dvejetainio indeksuoto medžio dydis yra lygus įvesties masyvo dydžiui, pažymėtam n. Toliau pateiktame kode naudojame n+1 dydį, kad būtų lengviau įgyvendinti.
Statyba
Visas BITree[] reikšmes inicijuojame kaip 0. Tada iškviečiame update() visiems indeksams, o update() operacija aptariama toliau.
Operacijos
getSum(x): grąžina pomasyvo masyvo [0,…,x] sumą
// Grąžina pomasyvo masyvo [0,…,x] sumą naudojant BITree[0..n], kuri yra sudaryta iš arr[0..n-1]
1) Išvesties sumą inicijuokite kaip 0, dabartinį indeksą kaip x+1.
2) Atlikite toliau nurodytus veiksmus, kai dabartinis indeksas yra didesnis nei 0.
…a) Pridėkite BITree[indeksą] prie sumos
…b) Eikite į pirminį BITree[index]. Tėvą galima gauti pašalinus
paskutinis nustatytas bitas iš dabartinio indekso, ty indeksas = indeksas – (indeksas ir (-indeksas))
3) Grąžinimo suma.
Aukščiau pateiktoje diagramoje pateikiamas pavyzdys, kaip veikia getSum(). Štai keletas svarbių pastebėjimų.
BITree[0] yra netikras mazgas.
BITree[y] yra BITree[x] pirminis, tada ir tik tada, kai y galima gauti pašalinus paskutinį nustatytą bitą iš dvejetainio x vaizdavimo, tai yra y = x – (x & (-x)).
Mazgo BITree[y] antrinis mazgas BITree[x] saugo elementų sumą tarp y (imtinai) ir x (išskyrus): arr[y,…,x).
update(x, val): atnaujina dvejetainį indeksuotą medį (BIT) atlikdama arr[index] += val
// Atminkite, kad atnaujinimo (x, val) operacija arr[] nepakeis. Tai tik keičia BITree[]
1) Inicijuokite dabartinį indeksą kaip x+1.
2) Atlikite šiuos veiksmus, kol dabartinis indeksas yra mažesnis arba lygus n.
…a) Pridėkite val prie BITree[index]
…b) Eikite į kitą BITree[index] elementą. Kitas elementas gali būti gaunamas padidinus paskutinį dabartinio indekso nustatytą bitą, ty indeksas = indeksas + (indeksas & (-index))
Atnaujinimo funkcija turi užtikrinti, kad visi BITree mazgai, kurių diapazone yra arr[i], būtų atnaujinti. Mes apjungiame tokius mazgus BITree, pakartotinai pridėdami dešimtainį skaičių, atitinkantį paskutinį dabartinio indekso bitą.
Kaip veikia dvejetainis indeksuotas medis?
Idėja pagrįsta tuo, kad visi teigiami sveikieji skaičiai gali būti pavaizduoti kaip 2 laipsnių suma. Pavyzdžiui, 19 gali būti pavaizduotas kaip 16 + 2 + 1. Kiekvienas BITree mazgas saugo n elementų sumą, kur n yra a Pavyzdžiui, pirmiau pateiktoje diagramoje (schemoje getSum()) pirmųjų 12 elementų suma gali būti gaunama iš paskutinių 4 elementų (nuo 9 iki 12) ir 8 sumos. elementai (nuo 1 iki 8). Dvejetainiame skaičiaus n atvaizde nustatytų bitų skaičius yra O(Logn). Todėl tiek getSum(), tiek update() operacijose perkeliame daugiausiai O(Logn) mazgų. Konstrukcijos sudėtingumas laike yra O(nLogn), nes jis kviečia update() visiems n elementų.
Įgyvendinimas:
Toliau pateikiami dvejetainio indeksuoto medžio diegimai.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Įvesties masyve esančių elementų skaičius.>> > // 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 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 -->Įvesties masyve esančių elementų skaičius.>> >Indexed Tree.> >arr[0..n-1] -->Įvesties masyvas, kurio priešdėlio suma> >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 -->Įvesties masyve esančių elementų skaičius.>> >Indexed Tree.> >arr[0..n-1] -->Įvesties masyvas, kurio priešdėlio suma> >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
elektroninės bankininkystės apribojimai
> // Javascript program to demonstrate lazy> // propagation in segment tree> > // Max tree size> let MAX = 1000;> let BITree=>new> Array(MAX);> > /* n -->Įvesties masyve esančių elementų skaičius.>> >arr[0..n-1] -->Įvesties masyvas, kurio priešdėlio suma> >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> |
>
>Išvestis
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Laiko sudėtingumas: O(NLogN)
Pagalbinė erdvė: O(N)
Ar galime išplėsti dvejetainį indeksuotą medį, kad būtų galima apskaičiuoti diapazono sumą O (logn) laiku?
Taip. rangeSum(l, r) = getSum(r) – getSum(l-1).
Programos:
Aritmetinio kodavimo algoritmo įgyvendinimas. Dvejetainio indeksuoto medžio kūrimą pirmiausia paskatino jo taikymas šiuo atveju. Matyti tai daugiau detalių.
Problemų pavyzdžiai:
Skaičiuokite inversijas masyve | 3 rinkinys (naudojant BIT)
Dviejų dimensijų dvejetainis indeksuotas medis arba Fenviko medis
Trikampių skaičiavimas stačiakampėje erdvėje naudojant BIT
Nuorodos:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees