2020-09-05 (Sat.)
モノイド \((X, \times)\) があるとする. これが主たる興味の対象であり, \(x \times y\) の \(\times\) は略して単に \(xy\) と書くことにする.
ここに \(X\) に対する右作用 \(M\) を用意する. これは作用適用の演算 \(@ \colon X \times M \to X\) を伴う: \[x \in X, m \in M, (x, m) \mapsto x@m \in X\] この \(@m\) を一括にして考えるとこれは \(X \to X\) なる写像だと思えて, これを作用という. \(x\) に \(m\) を作用させる, などと言ったりもする.
ここで作用 \(M\) がモノイド作用であるとは \(M\) 自体がまたモノイドであること. すなわち適当な乗算 \(\bullet\) があって \((M, \bullet)\) がモノイドであること. やはり \(\bullet\) を略して \(m_1 \bullet m_2\) を単に \(m_1 m_2\) などと書く.
加えて, 作用が準同型であることを要請する:
次のようなものはモノイド作用付きモノイドである.
この \(::\) はいわゆる代入と呼ばれる操作であり, ただし \(\top\) のときは代入しないことを表す. すなわち \(m \in M\) はデータを値 \(m\) で上書きするという操作を意味している.
遅延セグメントツリーはセグメントツリーのアップグレード版なので, まず先にただのセグメントツリーの説明をする.
一点更新, 区間取得が出来るセグメントツリーがある. これは次のようなものだった.
モノイド \((X, \times)\) と \(X\) の元からなる数列 \(x_1, x_2, \ldots, x_N\) について次の操作が高速に出来るようなデータ構造.
このデータ構造は具体的には次のように構成される.
添字に関する区間 \([i, i + 2^m)\) (\(m=0,1,2\ldots\)) に対してノードを用意する. 区間の包含関係によってエッジを張ればこれは二分木になる. すなわち, 区間 \(I_1 \supset I_2\) のとき, \(I_1\) を \(I_2\) の親とする. 区間 \(I\) に対応するノードのことも単にノード \(I\) と呼んでしまうことにする.
各ノード \(I\) に値として積 \(\prod_{i \in I} x_i\) を書いておく. ノード \(I\) に対応づける値を \(x(I)\) と書く. 特に, 二分木の葉は一点からなる区間 \([i, i+1)\) であり, \(x[i, i+1) = x_i\) である.
この値をノードごとに計算すると大変だけど, \(X\) がモノイドであることを利用して（結合則）, \[x(I_1 \cup I_2) = x(I_1) \times x(I_2)\] というマージが出来るので, 葉から順にボトムアップに計算すれば, 各ノードに対応する値 \(x\) はいつも \(O(1)\) で計算できる. ノード数は \(2N-1\) だから全体の初期化は \(O(N)\) で完了する.
\(x_i\) の値を更新することを考える. これで変わるべき \(x\) の値は \(i\) を含む区間の値で, それは二分木の高さ \(O(\log N)\) 個程度である. というわけでそこだけ実際に更新してしてしまえばよい. ノードに対して更新後の値の計算もやはり葉から順に計算すればノードごとに \(O(1)\).
次に区間取得とは \(x\) という表記方法を流用すれば, 自由な区間 \(J\) に対する \(x(J) = \prod_J x_j\) を計算することだと言い換えられる. もちろん \(J = [i, i + 2^m)\) という形をしていれば, これは計算済みであるが, 一般にはまだ分からない. しかし十進数がつねに二進数表示できるように, 任意の区間はこの形の区間に分割できる. そのような分割の中で最小のものを作ってその積を取れば良い.
最小な分割の作り方だが, これは貪欲に大きな区間をとっていけば良いだけで, しかも, たかだか \(O(\log N)\) 個の分割になる.
セグメントツリーの更新がちょうど一点に対してしか出来なかったのを区間に対して行えるように拡張したもの. アイデアとして, 更新をするときに \(x[i, i+1)\) を置き換えるだけでなくその親の値全てを書き換えてたが, これを必要になるときまで行わない. 代わりに, 遅延させておいた更新操作を各ノードに対して記録しておく. 必要になったらその操作を適用する.
データ構造はほとんどセグメントツリーと同じで, 区間 \(I = [i, i + 2^m)\) に対応してノード \(I\) があり, 値 \(x(I)\) を持つ. さて更新という操作をモノイド \(X\) に対するモノイド作用 \(M\) だと思うことにする. 区間に対する更新も, \(x(I)\) と同様に \(m(I) \in M\) として持っておく. 初期値は単位元 \(m(I) = 1_M\) にしておく.
ノード \(I\) の値が \(x(I)\) で作用が \(m(I)\) であるというのは次のような状況を意味している.
ノード \(I\) で作用を伝播させるとは次の操作を言う.
ただし \(m(I)=1\) のときはこれらの操作は行わないのと同じなのでスキップしてしまうように実装するのが良い.
任意の区間 \(J\) に含まれる各値 \(x_j\) に対して \(n \in M\) を作用することをここでは区間の更新という.
根のノード \(I=[1,2,\ldots,2^M]\) から始めてノードごとに区間更新をする
こちらも, 根から順に伝播しながら必要な区間にアクセスしていく. やはり根ノード \(I\) からスタートして次を実行する.