Disjoint Sparse Table

• Disjoint Sparse Table と セグ木に関するポエム - noshi91のメモ

• 長さ $N$ の静的な数列に対し、区間和、区間xor など、区間に対するクエリに高速に答えられる
• 載せるのはモノイドである必要がある。ざっくりいうと、結合律が成り立つ必要がある¹⁾
  • モノイド
  • 結合律: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
    • ○: 足し算＋、かけ算×、最小値などいろいろ
    • ×: べき乗（$(2^3)^2=8^2=64, \ 2^{(3^2)}=2^9=512$）など
• クエリ処理は速い $O(1)$
• 事前計算の計算量・メモリは少し多めに必要になる $O(N \log{N})$
• 更新はできない

ただ、使いどころは難しい。代替手段がいろいろある。

• 結合則に加えて冪等性（$A \oplus A = A$）も満たせば、（Disjointでない）通常の Sparse Tableを使える
  • min, max, gcd, bitwise-and, bitwise-or など
  • 通常の方が、構造が単純で理解しやすい
• モノイドに加えて、逆元（逆演算）があれば、累積和の差分で計算でき、事前計算量・必要メモリもこっちの方がよい
  • 和、xor など
• クエリ計算量にlogが付くことを許容すれば、SegmentTreeを使った方が、事前計算量は小さく、更新もできて汎用性が高い
  • 配列長 $N$ とクエリ数 $Q$ が同程度の場合、総合的にはあまり変わらない
• 参考
  • 分割統治による静的列の区間積クエリ | maspyのHP
  • 計算量が「モノイドの元同士の演算 ＞ モノイドの元に要素を1つ追加する処理」の場合、セグメント木より優位になることがある
    • 元同士の演算: $(A_i \oplus A_{i+1} \oplus ... ) \oplus (A_j \oplus A_{j+1} \oplus ...)$
    • 元に要素を1つ追加: $(A_i \oplus A_{i+1} \oplus ... ) \oplus A_j$
    • セグメント木は前者の回数が多くなるが、DSTは後者を多くおこなうため
    • 例) 元が集合であり、（要素数の上限はそこまで大きくないものの）区間が長いほど要素数が多くなる場合など

冪等性、逆演算は無いけど、クエリに対する計算量はとにかく高速にしたい！という時に使う。
また、[参考]のとおり、少し高度な問題ではセグメント木と比較して計算量が削減できる場合がある。
強いて言えば、ライブラリ化してしまえば実装の複雑性は気にしなくていいので、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つの区間の和で答えが求められる。

• 例)
  • $[3,13]$ を求めたい場合、階層1でまたぐので、$[3,7]+[8,13]$ で求められる
  • $[5,7]$ を求めたい場合、階層3でまたぐので、$[5,5]+[6,7]$ で求められる

またぐ階層を上から調べていたらクエリ毎に $O(\log{N})$ かかってしまうが、indexによい性質がある。

元の数列の長さを $2^n$ とする。

すると、クエリ $[L,R]$ に対して、$L \ xor \ R$ が、使用する階層を示している。

• $L \ xor \ R$ の最も左で立っているbitが（$2^{n-1}$ の桁から数えて）$k$ 番目なら、階層 $k$ を用いる
• 例)
  • $[3, 13]$ なら、$0011 \ xor \ 1101 = 1110$ なので、階層1を用いる
  • $[5, 7]$ なら、$0101 \ xor \ 0111 = 0010$ なので、階層3を用いる

要は「上の桁から見て $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次元配列で事前計算結果を保持する。実装方法はいろいろある。

• Disjoint Sparse Table と セグ木に関するポエム - noshi91のメモ
• Disjoint-Sparse-Table | Luzhiled’s Library
• 最小共通祖先 (Disjoint Sparse Table) - yaketake08's 実装メモ

基本的には、階層ごとに「idx ～ 対応する起点」の事前計算結果を持たせておく。 対応する起点が自身より右だったり左だったりする点に注意。

• $table[i][j]=$ 階層 $i$ における、idx=$j$～($j$ に対応する累積和の起点) までの和

階層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}$ 個まで計算するようになっている。

• 例) $n=4$ において階層 $i=1$ では、起点 3-4、11-12 から左右にそれぞれ $2^{4-1-1}=4$ 個ずつの累積和を計算している

また、累積和の起点（の右側の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$ とする。

• $L \ xor \ R$ を計算する。bit_lengthを $k$ とする
• $table[n-k][L] \oplus table[n-k][R]$ を計算する

このbit_lengthを求める操作に、言語によっては $O(\log{N})$ や $O(\log{\log{N}})$ かかることもあるかもしれない（が、まぁ無視してええやろ）

Pythonでは、int.bit_length()は（巨大数で無ければ）$O(1)$ で計算できるらしい。

• Worst-case time complexity of Python's int.bit_length() - Stack Overflow
• cpython/Objects/longobject.c at e4c431ecf50def40eb93c3969c1e4eeaf7bf32f1 · python/cpython · GitHub