競プロ用ライブラリを作る Advent Calendar 2024の12日目です.
SparseTableって?
長さ$N$の列が与えられたとき,「指定された区間の最小値を求めろ」のようなクエリを$O(1)$で処理できるデータ構造です.
ただし構築には$O(N\log N)$かかります.
仕組み
区間の最小値を求めるSparseTableを実装することを考えます.
長さ$N$の数列$x_0,x_1,\dots,x_{N-1}$について, 区間$[l, r)$の最小値を$x[l, r)$と書くことにします.
クエリを$O(1)$で処理したいだけなら, 全ての区間の答えを計算しておけばいいですが, 区間が$\Theta(N^2)$個あるのでこの方法は構築に$\Omega(N^2)$かかってしまいます.
SparseTableは幾つかの区間の情報だけ前計算しておいて, クエリで与えられる区間を前計算した区間2つの組み合わせで表現できるようにします.
例えば長さ5の数列が与えられたとき, $x[0,1), x[1,2), x[2,3), x[3,4), x[4,5), x[0,3), x[1,4], x[2,5)$の8つの情報を持っておけば, その中から2つ選んで全ての区間での答えを復元できます.
注目すべきが$x[0,5)$というクエリで, $\min(x[0,3),x[2,5))$という風に計算します. 持ってる情報が最小値なので区間に重複が出ても問題ないのがポイントです.
ここからはパズルです. 持つ情報を減らしつつ全ての区間の答えを2つの情報の組み合わせで表現するにはどうするのが効率的でしょうか.
AtCoderにそういう問題もあるのでどうぞ
答えの1つが「長さが2の冪の区間の情報だけ持つ」です.
例えば$x[l, r)$というクエリを捌くには長さ$M=2^{\lfloor\log_2(r-l)\rfloor}$の区間を2つ組み合わせます.
$x[l, r) = \min(x[l,l+M), x[r-M,r))$という感じですね. $M\le r-l$なので, これでクエリの区間からはみ出さず, クエリの区間内の全ての要素を捉えることが出来ます.
純粋に何も知らずに考察したら「長さが2の冪-1の区間の情報を持つ」になりそうですが, 2の冪の区間の情報を持った方がデータ量は少し増えますがちょっと簡潔になります.
実装
配列1つに頑張って全部の区間の情報を並べました. 計算をゴリゴリしたら出ます.
まとめ
いかがでしたか?
明日は今日に引き続き, 別にSegmentTreeで十分な気もするデータ構造を実装します.