Розглянемо наступну проблему, щоб зрозуміти бінарне індексоване дерево.
У нас є масив arr[0 . . . n-1]. Ми б хотіли
1 Обчисліть суму перших i елементів.
2 Змінити значення зазначеного елемента масиву arr[i] = x, де 0 <= i <= n-1.
А просте рішення полягає в тому, щоб запустити цикл від 0 до i-1 і обчислити суму елементів. Щоб оновити значення, просто виконайте arr[i] = x. Перша операція займає O(n) часу, а друга – O(1). Ще одне просте рішення — створити додатковий масив і зберегти суму перших i-х елементів за i-м індексом у цьому новому масиві. Суму даного діапазону тепер можна обчислити за O(1) часу, але операція оновлення зараз займає O(n) часу. Це добре працює, якщо існує велика кількість операцій запиту, але дуже мала кількість операцій оновлення.
Чи можемо ми виконати і запит, і операцію оновлення за O(log n) часу?
Одним з ефективних рішень є використання дерева сегментів, яке виконує обидві операції за час O (Logn).
Альтернативним рішенням є бінарне індексоване дерево, яке також досягає часової складності O(Logn) для обох операцій. Порівняно з деревом сегментів, бінарне індексоване дерево потребує менше місця та його легше реалізувати. .
Представництво
Двійкове індексоване дерево представляється у вигляді масиву. Нехай масив буде BITree[]. Кожен вузол бінарного індексованого дерева зберігає суму деяких елементів вхідного масиву. Розмір бінарного індексованого дерева дорівнює розміру вхідного масиву, позначеному як n. У наведеному нижче коді ми використовуємо розмір n+1 для зручності реалізації.
Будівництво
Ми ініціалізуємо всі значення в BITree[] як 0. Потім ми викликаємо update() для всіх індексів, операція update() описана нижче.
Операції
getSum(x): повертає суму підмасиву arr[0,…,x]
// Повертає суму підмасиву arr[0,…,x] за допомогою BITree[0..n], який складається з arr[0..n-1]
1) Ініціалізуйте вихідну суму як 0, поточний індекс як x+1.
2) Виконайте наступне, поки поточний індекс більше 0.
…a) Додайте BITree[index] до суми
…b) Перейдіть до батьківського BITree[index]. Батьківський можна отримати шляхом видалення
останній встановлений біт із поточного індексу, тобто індекс = індекс – (індекс & (-індекс))
3) Повернути суму.
На діаграмі вище показано, як працює getSum(). Ось кілька важливих зауважень.
BITree[0] є фіктивним вузлом.
BITree[y] є батьком BITree[x] тоді і тільки тоді, коли y можна отримати шляхом видалення останнього встановленого біта з двійкового представлення x, тобто y = x – (x & (-x)).
Дочірній вузол BITree[x] вузла BITree[y] зберігає суму елементів між y (включно) та x (виключно): arr[y,…,x).
update(x, val): оновлює двійкове індексоване дерево (BIT), виконуючи arr[index] += val
// Зауважте, що операція update(x, val) не змінить arr[]. Він вносить зміни лише в BITree[]
1) Ініціалізуйте поточний індекс як x+1.
2) Виконайте наступне, поки поточний індекс менший або дорівнює n.
…a) Додайте значення до BITree[index]
…b) Перейти до наступного елемента BITree[index]. Наступний елемент можна отримати шляхом збільшення останнього встановленого біта поточного індексу, тобто індекс = індекс + (індекс & (-індекс))
Функція оновлення має переконатися, що всі вузли BITree, які містять arr[i] у своїх діапазонах, оновлюються. Ми перебираємо такі вузли в BITree, неодноразово додаючи десяткове число, що відповідає останньому встановленому біту поточного індексу.
Як працює бінарне індексоване дерево?
Ідея базується на тому факті, що всі додатні цілі числа можна представити як суму степенів 2. Наприклад, 19 можна представити як 16 + 2 + 1. Кожен вузол BITree зберігає суму з n елементів, де n є a ступінь 2. Наприклад, на першій діаграмі вище (діаграма для getSum()) суму перших 12 елементів можна отримати за допомогою суми останніх 4 елементів (від 9 до 12) плюс сума 8 елементів (від 1 до 8). Кількість встановлених бітів у двійковому представленні числа n дорівнює O(Logn). Таким чином, ми проходимо щонайбільше O(Logn) вузлів в обох операціях getSum() і update(). Часова складність конструкції становить O(nLogn), оскільки вона викликає update() для всіх n елементів.
Реалізація:
Нижче наведено реалізацію бінарного індексованого дерева.
C++
// C++ code to demonstrate operations of Binary Index Tree> #include> > using> namespace> std;> > /* n -->Кількість елементів у вхідному масиві.> >BITree[0..n] -->Масив, який представляє бінарне індексоване дерево.> >arr[0..n-1] -->Вхідний масив, для якого обчислюється префіксна сума. */> > // 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
// 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 -->Кількість елементів у вхідному масиві.> >BITree[0..n] -->Масив, який представляє двійковий> >Indexed Tree.> >arr[0..n-1] -->Вхідний масив, для якого сума префікса> >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> |
numpy унікальний
>
>
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 -->Кількість елементів у вхідному масиві.> >BITree[0..n] -->Масив, який представляє двійковий> >Indexed Tree.> >arr[0..n-1] -->Вхідний масив, для якого сума префікса> >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 -->Кількість елементів у вхідному масиві.> >BITree[0..n] -->Масив, який представляє двійковий> >Indexed Tree.> >arr[0..n-1] -->Вхідний масив, для якого сума префікса> >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> |
>
>Вихід
Sum of elements in arr[0..5] is 12 Sum of elements in arr[0..5] after update is 18>
Часова складність: O(NLogN)
Допоміжний простір: O(N)
Чи можемо ми розширити бінарне індексоване дерево для обчислення суми діапазону за час O(Logn)?
Так. rangeSum(l, r) = getSum(r) – getSum(l-1).
Застосування:
Реалізація алгоритму арифметичного кодування. Розробка бінарного індексованого дерева була в першу чергу мотивована його застосуванням у цьому випадку. Побачити це для більш детальної інформації.
Приклад проблем:
Підрахувати інверсії в масиві | Набір 3 (з використанням BIT)
Двовимірне бінарне індексоване дерево або дерево Фенвіка
Підрахунок трикутників у прямокутному просторі за допомогою BIT
Література:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees