Binary Indexed Tree を理解するために次の問題を考えてみましょう。
配列 arr[0 . 。 。 n-1]。私たちはしたい
1 最初の i 要素の合計を計算します。
2 配列 arr[i] = x (0 <= i <= n-1) の指定された要素の値を変更します。
あ 簡単な解決策 0 から i-1 までループを実行し、要素の合計を計算します。値を更新するには、単に arr[i] = x を実行します。最初の操作には O(n) 時間がかかり、2 番目の操作には O(1) 時間がかかります。もう 1 つの簡単な解決策は、追加の配列を作成し、最初の i 番目の要素の合計をこの新しい配列の i 番目のインデックスに格納することです。指定された範囲の合計は O(1) 時間で計算できるようになりましたが、更新操作には O(n) 時間かかります。これは、クエリ操作が多数あるものの、更新操作の数が非常に少ない場合にうまく機能します。
クエリと更新の両方の操作を O(log n) 時間以内に実行できるでしょうか?
効率的な解決策の 1 つは、両方の操作を O(Logn) 時間で実行するセグメント ツリーを使用することです。
代替ソリューションはバイナリ インデックス ツリーであり、これも両方の操作で O(Logn) 時間の複雑さを実現します。セグメント ツリーと比較して、バイナリ インデックス付きツリーは必要なスペースが少なく、実装が簡単です。 。
表現
バイナリ インデックス付きツリーは配列として表されます。配列を BITree[] とします。バイナリ インデックス付きツリーの各ノードには、入力配列のいくつかの要素の合計が格納されます。バイナリ インデックス付きツリーのサイズは、n で示される入力配列のサイズと等しくなります。以下のコードでは、実装を容易にするために n+1 のサイズを使用します。
工事
BITree[] 内のすべての値を 0 として初期化します。次に、すべてのインデックスに対して update() を呼び出します。update() 操作については以下で説明します。
オペレーション
getSum(x): サブ配列 arr[0,…,x] の合計を返します。
// BITree[0..n] を使用してサブ配列 arr[0,…,x] の合計を返します。これは arr[0..n-1] から構築されます。
1) 出力合計を 0、現在のインデックスを x+1 として初期化します。
2) 現在のインデックスが 0 より大きい間に次の操作を実行します。
…a) BITree[index] を合計に加算します
…b) BITree[index] の親に移動します。親は削除することで取得できます。
現在のインデックスから最後に設定されたビット、つまり、インデックス = インデックス – (インデックス & (-インデックス))
3) 合計を返します。
上の図は、getSum() がどのように動作するかを示す例です。ここでいくつかの重要な観察を示します。
BITree[0]はダミーノードです。
BITree[y] は、x のバイナリ表現から最後に設定されたビットを削除することによって y を取得できる場合、つまり y = x – (x & (-x)) である場合に限り、BITree[x] の親になります。
ノード BITree[y] の子ノード BITree[x] には、y (両端を含む) と x (両端を含まない) の間の要素の合計、arr[y,…,x) が格納されます。
PowerShell の複数行コメント
update(x, val): arr[index] += val を実行してバイナリ インデックス ツリー (BIT) を更新します。
// update(x, val) 操作では arr[] が変更されないことに注意してください。 BITree[] にのみ変更を加えます。
1) 現在のインデックスを x+1 として初期化します。
2) 現在のインデックスが n 以下である間に次の操作を実行します。
…a) val を BITree[index] に追加します。
…b) BITree[index] の次の要素に移動します。次の要素は、現在のインデックスの最後に設定されたビットをインクリメントすることによって取得できます。つまり、インデックス = インデックス + (インデックス & (-インデックス))
更新関数は、範囲内に arr[i] を含むすべての BITree ノードが更新されていることを確認する必要があります。現在のインデックスの最後に設定されたビットに対応する 10 進数を繰り返し加算することによって、BITree 内のそのようなノードをループします。
バイナリインデックスツリーはどのように機能しますか?
このアイデアは、すべての正の整数が 2 のべき乗の合計として表現できるという事実に基づいています。たとえば、19 は 16 + 2 + 1 として表現できます。BITree のすべてのノードは、n 個の要素の合計を格納します。ここで、n はたとえば、上の最初の図 (getSum() の図) では、最初の 12 要素の合計は、最後の 4 要素 (9 から 12) の合計と 8 の合計によって取得できます。要素 (1 ～ 8)。数値 n の 2 進数表現における設定ビット数は O(Logn) です。したがって、getSum() 操作と update() 操作の両方で最大でも O(Logn) ノードを走査します。すべての n 要素に対して update() を呼び出すため、構築の時間計算量は O(nLogn) です。
実装：
以下は、Binary Indexed Tree の実装です。
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 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] -->バイナリを表す配列>>' >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> 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> |
>
>
数学ランダムJava
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] -->バイナリを表す配列>>' >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> 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] -->バイナリを表す配列>>' >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[].> 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(Logn) 時間で範囲の合計を計算することはできますか?
はい。 rangeSum(l, r) = getSum(r) – getSum(l-1)。
アプリケーション:
算術符号化アルゴリズムの実装。バイナリ インデックス ツリーの開発は、主にこの場合のアプリケーションによって動機付けられました。見る これ 詳細については。
問題例:
配列内の反転をカウントする |セット 3 (BIT を使用)
2 次元バイナリ インデックス ツリーまたはフェンウィック ツリー
BIT を使用して長方形空間内の三角形を数える
参考文献:
http://en.wikipedia.org/wiki/フェンウィック_ツリー
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees