2次元遅延セグ木の見果てぬ夢

$2$ 次元遅延セグ木は (かなり制限した設定でも) 実現不能と考えられている (以下の資料を参照せよ)。

勉強会をしました。今日のテーマは「2次元セグメント木」です。スライドを公開します。https://t.co/tL8fMsdBv3
— こたつがめ (@kotatsugame_t) 2024年3月18日

本記事では、 $2$ 次元遅延セグ木になれそうでなれないデータ構造たちを紹介する。

可換モノイドの長方形加算長方形和

$(M, +, 0)$ を可換モノイドとし、 $M$ の $2$ 次元列 $a \in M ^ {H \times W}$ を考える。以下のクエリを $\Theta ( \log (H) \log (W) )$ の時間計算量で処理する。

$\mathtt { add }$ : $l, r, d, u \in \mathbb{Z} , x \in M$ が指定され、 $(i , j) \in \lbrack l, r) \times \lbrack d, u)$ について $a _ {i , j} \gets a _ {i , j} + x$ と更新する。
$\mathtt { sum }$ : $l, r, d, u \in \mathbb{Z}$ が指定され、 $\displaystyle \sum _ { (i , j) \in \lbrack l, r) \times \lbrack d, u) } a _ { i , j }$ を出力する。

基本となる知識は区間mul 区間積 O(log N) - よすぽの日記この記事で説明されているデータ構造である。まず、上述のセグ木を $H$ 本用意し、 $i$ 本目のセグ木は $a _ { i , \ast }$ を管理するものとする。セグ木のノードを配列に展開すれば ( $2$ 種類の値を管理するが、適当に並べておく) このセグ木群は $2$ 次元配列と見做すことができ、 $\mathrm { seg } _ {i , k}$ が $i$ 本目のセグ木の $k$ 番目のノードを表す。

$\mathtt { add }$ クエリの処理を考えると、 $i \in \lbrack l , r )$ について、 $\mathrm{seg} _ i$ に $\lbrack d , u )$ への $x$ の区間加算を行うことになる。さらに区間加算の内部の処理を考えると、「 $k, c$ が与えられて、 $i \in \lbrack l , r )$ について $\mathrm{seg} _ {i , k} \gets \mathrm{seg} _ {i , k} + c$ 」という操作 $\Theta ( \log (W) )$ 回で表されることが分かる *1。すると、 $\mathrm { seg }$ を転置して $b _ k := ( \mathrm{seg} _ {i , k} ) _ {i = 0} ^ {H - 1}$ を $1$ つの列として管理したとき、 $b _ k$ への区間加算で操作が表されることになる。これは $b _ k$ たちを区間加算セグ木で管理すれば $\Theta ( \log (H) \log (W) )$ で実行できる。

$\mathtt { sum }$ クエリも、和の順序を適切に入れ替えれば $b _ k$ に対する区間和クエリを用いてシミュレートできることが分かる。

あり得そうな使いどころとしては、 $(M , + , 0) = (\mathbb{Z} , + , 0)$ や $(M , + , 0) = (\mathbb{Z} , \min , \infty)$ が挙げられる。その場合は冪乗が $\Theta ( 1 )$ で求まるため、上記のアルゴリズムのうち複数の部分が簡略化、効率化されるだろう。

kd-tree

可換モノイド $M$ と作用 $F$ が遅延セグ木の要件を満たすとする。 $2$ 次元平面に $N$ 個の点からなる点群 $P$ があり、各点 $p \in P$ が値 $a _ p \in M$ を持っているとき、以下のクエリを $\Theta ( \sqrt N )$ の時間計算量で処理する。

$\mathtt { apply }$ : $l, r, d, u \in \mathbb{Z} , f \in F$ が指定され、 $p \in \lbrack l, r) \times \lbrack d, u)$ について $a _ p \gets f (a _ p)$ と更新する。
$\mathtt { prod }$ : $l, r, d, u \in \mathbb{Z}$ が指定され、 $\displaystyle \prod _ { p \in \lbrack l, r) \times \lbrack d, u) } a _ p$ を出力する。

kd-tree については検索すれば様々な資料が見つかるはずである。注意点として、kd-tree はユークリッド距離での最近点の検索によく使われるが、そちらの計算量を保証するには点群のランダム性が必要となる。

kd-tree は $P$ を $x$ 座標の大小で半分に分け、それらを $y$ 座標の大小で半分に分け、... と軸を交互に切り替えながら点群を分割していく過程を $2$ 分木にしたものである。各ノードが対応する点群についての $a _ p$ の総積などを持てば、( $1$ 次元の) 遅延セグ木と全く同様にしてクエリを処理することができる。すなわち、クエリの長方形 $\lbrack l , r ) \times \lbrack d , u )$ とノードの点群の bounding box の関係を見て、共通部分がないかクエリに包含されていれば直ちに return し、いずれでもなければ子に対して再帰的に処理を行う。

問題は、上記のように再帰を行ったときに訪れるノードの個数を抑えることである。観察すると、あるノードについての処理が子に再帰するとき、クエリの長方形の $4$ 辺のうち少なくとも $1$ 本がノードの bounding box と交差していることが分かる。そこで、軸に平行な直線 $\ell$ を任意にとり、 $\ell$ と bounding box が交差するようなノードの個数を考える。根から深さを $1$ ずつ増やしていくと、 $\ell$ と交差するノードの個数は深さが $2$ 増える毎に $2$ 倍になることが分かる。 kd-tree の深さは $\log _ 2 (N)$ であるから、 $\ell$ と交差するノードは全体で $\Theta ( \sqrt N )$ 個あることが分かる。長方形クエリの場合は $4$ 辺があるため、この $4$ 倍で抑えられることになる。

なお、kd-tree はオーダーが $\Theta ( \sqrt N )$ である上に定数倍があまり良くないため、思ったほど振り回せる道具ではない。

$4$ 分木

(※ 四分木 (Quadtree) と言うと kd-tree のように点群に対するデータ構造を指すようなので、この節のように行列に対するものには別の名前が付いているかもしれない。)

可換モノイド $M$ と作用 $F$ が遅延セグ木の要件を満たすとし、 $M$ の $2$ 次元列 $a \in M ^ {N \times N}$ を考える。以下のクエリを $\Theta ( N )$ の時間計算量で処理する。

$\mathtt { apply }$ : $l, r, d, u \in \mathbb{Z} , f \in F$ が指定され、 $(i, j) \in \lbrack l, r) \times \lbrack d, u)$ について $a _ { i , j} \gets f (a _ { i , j} )$ と更新する。
$\mathtt { prod }$ : $l, r, d, u \in \mathbb{Z}$ が指定され、 $\displaystyle \prod _ { (i , j) \in \lbrack l, r) \times \lbrack d, u) } a _ { i , j}$ を出力する。