[データ構造]バイナリインデックスツリー(フィンウィックツリー)

バイナリインデックスツリー

O(logn)O(logn)O(logn)O(logn)内で区間和のデータ構造を求めることができる.
では、なぜこのバイナリインデックスツリーを使用するのでしょうか.
アレイAが次のように仮定される.
A
1
2
0
4
1
3
5
9
8
6
このとき、PrefixSum(k)=A[i]+...+A[k]PrefixSum(k)= A[i] + ... + A[k]PrefixSum(k)=A[i]+...+A[k]と定義した場合,1≦k≦n 1leklen 1≦k≦nのため,時間的複雑度はO(n)O(n)O(n)O(n)で区間和を求めることができる.
このようなPrefixSumPrefixSumを検索するためにmmmを使用する場合、時間的複雑さはO(mn)O(mn)O(mn)O(mn)O(mn)である.
しかし,前処理は時間複雑度をO(m＋n)O(m＋n)O(m＋n)O(m＋n)に低減できる.
前処理プロセスを格納する配列Pを宣言し、P[k]=A[1]+...+A[k]P[k] = A[1] + ... + A[k]P[k]=A[1]+...+A[k]を保存する場合、配列Pは以下のようになります.
P
1
3
3
7
8
11
16
25
33
39
したがって、O(1)O(1)O(1)O(1)O(1)内でO(n)O(n)O(n)O(n)O(n)の区間和を直接求めることができます.
例えば、PrefixSum(5)PrefixSum(5)PrefixSum(5)=A[1]+...+A[5]=P[5]=8PrefixSum(5) = A[1] + ... + A[5] = P[5] = 8PrefixSum(5)=A[1]+...+なお、A[5]=P[5]=8である.
A配列の区間5から8ビットの和のsum(5,8)=A[5]+...+A[8]Sum(5,8) = A[5] + ... + A[8]Sum(5,8)=A[5]+...+A[8]では、時間的複雑度も同様にO(1)O(1)O(1)で求めることができる.
Sum(i,j)=A[i]+...+A[j]=P[j]−P[i−1]Sum(i,j) = A[i] + ... + A[j] = P[j] - P[i-1]Sum(i,j)=A[i]+...+A[j]=P[j]すなわちP[i 1]であるため、前処理プロセスは、時間的複雑度をO(1)O(1)O(1))として迅速に求めることができる.
ただし,Aアレイの5番目の位置の値が1ではなく3になると,区間和を求める前処理アレイを再解く必要がある.
これらの配列のk位置の値をxに変換する関数をupdate(k,x)update(k,x)update(k,x)update(k,x)update(k,x)と呼び,配列を前処理するのに要する時間複雑度をO(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)
このとき、バイナリインデックスツリーを使用すると、更新(k,x)更新(k,x)更新(k,x)を実行する際に、O(logn)O(logn)O(logn)で前処理配列を再取得することができる.
まず、バイナリインデックスツリーとして使用する配列Tを宣言する.
PrefixSum(6)=(A[6]+A[5])(+...+A[2]+A[1])PrefixSum(6) = (A[6] + A[5]) (+ ... + A[2] +A[1])PrefixSum(6)=(A[6]+A[5])(+...+A[2]+A[1])
T[6]=A[6]+A[5]T[6] = A[6] + A[5]T[6]=A[6]+A[5]
T[4]=A[4]+A[3]+A[2]+A[1]T[4] = A[4] +A[3] +A[2] + A[1]T[4]=A[4]+A[3]+A[2]+A[1]
prefixSum(10)=A[10]+...A[1]prefixSum(10) = A[10] + ... A[1]prefixSum(10)=A[10]+...A[1]
T[10]=A[10]+A[9]T[10] = A[10] + A[9]T[10]=A[10]+A[9]
T[8]=A[8]+...+A[1]T[8] = A[8]+ ... + A[1]T[8]=A[8]+...+A[1]
次に,A配列の区間とTの各位置を次式のように配置する.
では、どのようにして各位置に格納する区間と別々に格納するのでしょうか.
T[k]=A[k]+...+A[k−LSB(k)+1]T[k] = A[k] +... +A[k-LSB(k)+1]T[k]=A[k]+...+A[k=LSB(k)+1]とともに保存します.
このとき,LSB(k)LSB(k)LSB(k)LSB(k)はkkkをビットとして表し,右端から左端に移動し,1番目の1が出現する位置がdの場合,2 d 2^d 2 dで解く.
したがって、k=6 k=6 k=6の場合、ビットを表すと110であり、最初の1が現れる位置dは1であるため、LSB(6)=21=2 LSB(6)=2^1=2 LSB(6)=21=21=21=2 LSB(6)=21=21=2となる.
従って、T[6]=A[6]+…+A[6−2+1]=A[6]+A[5]T[6] = A[6] + ... +A[6-2+1] = A[6] + A[5]T[6]=A[6]+...+A[6∮2+1]=A[6]+A[5]保存すればよい.
すべてのTスキームをこのように解くと、

では,LSB(k)LSB(k)LSB(k)LSB(k)LSB(k)の時間的複雑さはいったいどうだろうか.
LSB(k)LSB(k)LSB(k)LSB(k)LSB(k)を解くのは効率が悪いので,まずLSB(k)LSB(k)LSB(k)時間の複雑さを解く.
kビットが01110000であると仮定し、以下に示す.
このとき、kを求める2の報酬(=1の報酬+1)は、10010111+1=1001001001001001001011+1=1=1001001001001001011+1=10010010010010011001である.
これを&演算すると,LSB(k)LSB(k)LSB(k)LSB(k)LSB(k)LSB(k)を一定時間で求めることができる.
では,Tに格納された各区間の和をどのように利用して必要な区間の和を求めるのか.
「アレイT」では、各累積はツリーのような形で保存される.
このとき、累積和毎にLSBを用いてセグメント化されているので、要求解を求めるPrefixSum(k)PrefixSum(k)PrefixSum(k)を求める場合、開始位置をkとして保持し、k値が0になるまでLSB(k)LSB(k)LSB(k)LSB(k)(k)LSB(k)をkから減算し続け、Tアレイの位置を移動して区間毎の和を求めることができる.

def prefix_sum(k):
  s = 0
  while k>=1:     # 1의 개수만큼 복잡도를 가짐, k<=n, O(log n)
    s= s+T[k]
    k = k - LSB(k)
  return s

同様に、配列の値が変更された場合.

def update(k,x): #A[k] -> x로 체인지
  d= x-A[k]
  while k <= n:
    T[k] = T[k] + d
    k = k + LSB(k)

したがって,バイナリインデックスツリーを用いる場合,O(logn)O(logn)O(logn)O(logn)では各区間の和と変更を求めることができる.