ただ、使いどころは難しい。代替手段がいろいろある。
冪等性、逆演算は無いけど、クエリに対する計算量はとにかく高速にしたい!という時に使う。
また、[参考]のとおり、少し高度な問題ではセグメント木と比較して計算量が削減できる場合がある。
強いて言えば、ライブラリ化してしまえば実装の複雑性は気にしなくていいので、SparseTableの代わりに常にこっちを使うのはありかも。
冒頭のnoshi91氏の記事に図があるのでそれがわかりやすい。
ある数列($N=16$)の区間和を求めたいとする。
以下の区間和を事前計算して保存しておく。
階層1 idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------||----------------------| |-------------------||-------------------| |----------------||----------------| |-------------||-------------| |----------||----------| |-------||-------| |----||----| |-||-| 階層2 idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------||----------||----------||----------| |-------||-------| |-------||-------| |----||----| |----||----| |-||-| |-||-| 階層3 idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----||----||----||----||----||----||----||----| |-||-| |-||-| |-||-| |-||-| 階層4 idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-|
階層1での 7-8 や、階層2での 3-4、11-12 など、各階層ごとに、累積和が左右に伸び始めている“起点”がある。
クエリ $[L,R]$ に対し、上から調べてはじめて $[L,R]$ がその階層の起点をまたぐところで 左右の適切なindexをとれば、どのようなクエリに対しても2つの区間の和で答えが求められる。
またぐ階層を上から調べていたらクエリ毎に $O(\log{N})$ かかってしまうが、indexによい性質がある。
元の数列の長さを $2^n$ とする。
すると、クエリ $[L,R]$ に対して、$L \ xor \ R$ が、使用する階層を示している。
要は「上の桁から見て $L$ と $R$ が一番最初に異なっているbit」を求めているのだが、
各階層での累積和の起点は、ちょうどそこで2進数の $k$ 番目のbitが0→1へ繰り上がる位置となっている。
そこをまたぐ $L$ と $R$ はそのbitが確実に異なることになる。
階層1の起点付近 idx ... 6 7 | 8 9 ... ここをまたぐL,Rは bin 0110 0111 | 1000 1001 上から1桁目が異なる ~ ~ ~ ~ 階層2の起点付近 idx ... 2 3 | 4 5 ... 10 11 | 12 13 ... bin 0010 0011 | 0100 0101 ... 1010 1011 | 1100 1101 ... ~ ~ ~ ~ ~ ~ ~ ~ 上から2桁目が異なる
2次元配列で事前計算結果を保持する。実装方法はいろいろある。
基本的には、階層ごとに「idx ~ 対応する起点」の事前計算結果を持たせておく。 対応する起点が自身より右だったり左だったりする点に注意。
階層2 idx 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------||----------||----------||----------| |-------||-------| |-------||-------| |----||----| |----||----| |-||-| |-||-| table[2][ 1] = [ 1, 3] の累積和 table[2][13] = [12, 13] の累積和
区間を求めるデータ構造で、セグメント木などでは $[l,r)$ のように半開区間で指定することも多いが、 DSTでは階層を求める際に $[l,r]$ でxorを取る際、閉区間を想定しているため、 (少なくとも内部では)区間といったら閉区間、と決めてしまう方が一貫しているように思う。
ライブラリとして実装して、外部に公開するAPIの部分では、半開区間に揃えてやるのもあり。
$table[i][j]$ の $j$ の範囲は、元配列の長さ $N$ となるが、後ろを単位元で埋めて、2のべき乗に長さを揃えると実装しやすい。
しなくても理屈上はできるが、一番後ろのブロックだけ例外処理を行わないと範囲外参照を起こし、面倒になる。
ここまでの説明では階層は1から数えていたが、実装では0から数えることにする。
配列長を $2^n$ に揃えた場合、$table[i][j]$ で $0 \le i \lt n$、$0 \le j \lt 2^n$ の範囲を動く。
階層 $i$ では、起点から累積和を最大 $2^{n-i-1}$ 個まで計算するようになっている。
また、累積和の起点(の右側のindex)は、以下のようになっている。
|-- n bit ---| 01110...010000 n bit中、先頭 i bitが任意、i+1 bit目が"1"、残りが全て"0" |-------| i bit
よって、for文で $2^{n-i-1}$ からはじめて、$2^n$ まで $2^{n-i}$ ずつ加算してやれば、起点を列挙できる。
そこから左右に $2^{n-i-1}$ ずつ累積和を伸ばしていけばよい。
交換法則($A \oplus B = B \oplus A$)を満たさない演算の場合、累積和を取る方向によって、左からかけるか、右からかけるか、注意する。
まず、長さ1のクエリは、DSTでは対応できない。
(実装方法によっては、「左側長さ1の区間」+「右側長さ0の区間」のように、事前計算に長さ0の区間も含めることで対応可能)
長さ1のクエリに対する答えは、元の配列を直接参照すれば自明なので、例外処理して返す。
長さ2以上の場合、クエリには以下で答えられる。配列長を $2^n$ とする。
このbit_lengthを求める操作に、言語によっては $O(\log{N})$ や $O(\log{\log{N}})$ かかることもあるかもしれない(が、まぁ無視してええやろ)
Pythonでは、int.bit_length()は(巨大数で無ければ)$O(1)$ で計算できるらしい。