データ構造と代数(後編)

この記事はIS17er Advent Calendar 2016の13日目の記事です. 前日の記事データ構造と代数(前編)に対応した後編となっているので,まずはそちらをお読み下さい.

Segment Tree(つづき)

区間累積,区間更新SegTree

最後は区間での演算の累積と区間に対する一様な更新を同時にサポートするSegment Treeです.つまり,モノイド $(X, \ast)$ と作用素モノイド $M$ (演算子は省略して乗法的に書く)があって $M$ から $X$ への作用が定まっている時,$X$ 上の列 $(a_i)_{i=0}^{n-1}$ の区間での演算の累積(総乗)と $M$ からの区間への一様な作用の両方を扱えるものです.例えば区間に一様に1次関数を作用させつつ区間での最小値を求めたいなど.

区間への一様な作用とその実装については既に書いたので,後はそれと両立するように演算の累積の実現を考えればよいです.半分先に済ませてしまったので案外なんとかなりそうですね.

ただし,重要な制約が1つあります.各ノードは自身が対応している区間での演算の累積とそこへの一様な作用を記憶しますが,その区間への一様な作用が更新された時(新たに作用がきたとき),区間での演算の累積が定数時間で更新できる必要があります.

例えば,あるノードが対応づいている区間での最小値が $m$ で一様に $x$ 加算する更新が来たとすると,結果的にこの区間の最小値は $m + x$ になります.各元に $x$ 足してから $min$ をとるのと $x$ を足す前に $min$ をとって後から $x$ 足すのは同じなのでこのように更新できます(一様な定数加算は順序を保存する).

最初に挙げた例の1次関数の適用は少し注意が必要になります.元の最小値が $m$ で一様に適用された1次関数が $f$ だったとすると,$f$ が単調増加(グラフが傾きが非負の直線)の時に限って その区間での最終的な最小値は $f(m)$ になります.順序を保つことから各元に $f$ を適用してから $min$ をとったものと $min$ をとってから $f$ を適用したものは一致します.ところが $f$ が単調減少であった時は,各元に $f$ を適用した後 $min$ を取るのは $max$ を取ってから $f$ を適用するのに等しくなります.よって求められているのが $min$ であれ $max$ であれ両方必要なので,モノイドを $(X, min)$ から $(X \times X, min \times max)$ にしておかなければなりません(このときmaxも双対的に更新できます).

完全に不可能な例もあります.正整数の乗法的モノイドをべきとして作用させる( $x$ に $y$ を作用させると $x^y$ を返す)もとでRSQは恐らく実現できません.区間での総和を覚えていても,区間を一様にべき乗しようとすると当然和のべきとべきの和は全く違うのでどうしようもありません.先ほどみたいに簡単な工夫でなんとかなることもなさそうです(うまくやろうとすると各区間でのあらゆる対称式が必要になりそうなので)(なんとかなりそうだったら是非教えてください).

つまり,演算の累積を考えたいモノイドと作用させたいモノイドの他に, $$ dist(m, a_l \ast \cdots \ast a_{r-1}) = m.a_l \ast \cdots \ast m.a_{r-1} $$ を任意の $a$ の区間に対して満たすような定数時間で計算できる $dist: M \times X \rightarrow X$ が必要になります.作用と演算が可換な時(分配法則とも言えますね)はこれは単に作用演算と同じものですが,上の1次関数の適用と最小値クエリの例で見たようにそうでない時もあります.

ここさえ注意すれば,後は演算の累積を考えるだけです.区間に対する一様な作用は,作用の順序を壊しそうなところは予め壊れないところまで下向きに伝搬させておいてからいつものループで値を積んでいけば良いのでした.この時,値を積んだ所のノードの先祖の演算の累積は更新する必要があります(子孫が更新された=区間の一部が作用で変更された).しかしこれらは $l$ と $r-1$ に対応するノードの先祖のノードの集合の和に等しいということは先程述べたので,ここから今度は上に登っていけば良いです.

また,区間での演算の累積クエリ自体を考えます.いつものループで取り出した必要なノード達の値を累積するだけでは不十分なのはすぐ分かります.そこの上にまだ留まってる作用も考慮する必要があります.ようは再び上に留まった分をクエリで使うノードまで下ろしてくればいいので,作用クエリではじめにやったものと同じことをすれば良いことが分かります.ちなみに,累積は再帰関数で実装するといちいち作用を下ろしてくる操作は不要です.再帰関数は必ず根から呼び出すので,上の方に溜まっている作用のかぶり漏れがないです.といっても再帰関数は再帰呼出しの木の展開と基底ケース確定後の木の折りたたみで木を2往復してると見れるので,速度面でも優位かどうかは微妙です(後ほど確認します).案外やることは今までやったことの組み合わせでしかないので,実装はなんとかなりそうですね!

実装は後ほど追加します(ごめんなさい)

Binary Indexd Tree

Binary Indexd Treeは,Segment Treeの最も基本的なものの演算の累積を $a_0 \ast \cdots a_{r-1}$ の形に制限したものです.SegTreeに比べて省メモリでビット演算がいい感じに機能して定数倍高速,というような利点があります(非再帰版のSegTreeとはそこまで大きな差は開かないと思います).

本当に列の左端からの累積のみしか必要でないならそれで良いのですが,モノイドの任意の元が可逆,つまり群を成しているならSegTreeと全く同じ機能が実現できます.

実際 $accumulate(l) = a_0 \ast \cdots a_{r-1}$ なら $ a_l \ast \cdots a_{r-1} = accumulate(l)^{-1} \ast accumulate( r )$ で簡単に計算できます.

RSQの時はよく $accumulate( r ) - accumulate(l)$ と書くみたいですがこれは実数の和が可換だからで,そうじゃない時はこの順番で書くと間違いになるので注意してください.

この節はこれで終了です.ありがとございました.

ところで今のは嘘です. 本当の本当に適当に済ませすぎていた結果なんですが,BITは更新クエリに可換律が必要です.また逆元の存在を仮定しないなら,更新クエリは代入ではなくて各元に何かを演算させる(和のモノイドを考えているなら何かを足す等)ことしかできません.

Sparse Table

最後はSparse Tableです.動作原理は簡明なのでここで簡単に区間での $min$ を使って說明します.

まずはじめに,列の各元から右向きに2のべきの長さ手を伸ばした区間での $min$ を記録したテーブルを作ります.つまり $$ t_{i, j} = min(a[i, i+2^j)) $$ なる2次元配列 $t$ を作ります.$t_{i, j+1} = min(t_{i, j}, t_{i+2^j, j})$ なので,ループを適切に回せば $O(n \log n)$ で初期化できます.

そして,例えば $[0, 15)$ での最小値を求めたい時は,まず”2本でうまく区間をはみ出ず覆える2のべきになっている長さ”を計算して実際に覆います.この区間の幅は15なので,長さを8にすると良いですね(4だと足りないし,16までいくとはみ出ます).そして,左端から長さ8,右端から長さ8で区間を覆うとうまくいきます.つまり,$t_{0, 3}$ が $[0, 8)$ での最小値を,$t_{7, 3}$ が $[7, 15)$ での最小値を覚えているので,この2つのminを取れば $[0, 15)$ での最小値が計算できます.

このいい感じの”長さ”ですが,要は区間の長さの $log_2$ 相当の値なので,$O(\log n)$ で計算できます.しかし,予め計算してこれについてもテーブルを持っておくと良いです.このテーブル自体は空間 $O(n)$ しか取らず,そもそも $t$ が空間 $O(n \log n)$ なのでほとんど問題ないです.

こうすると,RMQが $O(1)$ で計算できます.これはSegTreeに対して真に有利な点となっています.その代わり,Sparse Tableは列の元の更新には基本対応していません.列のある元を変更した時に更新するべきテーブルの値が沢山あるというのはすぐに分かることです.さすがに1回の更新に $O(n \log n)$ かかるのでは対応しているとは言えません.

このSparse Tableがどのような代数構造上で動作するかを考えます.当然ですが,結合則は大前提です.よってまず半群であることは要請されます.これを今まで通り $(X, \ast)$ と書いて話を進めましょう.次に,”オーバーラップしても問題ない”というのも必要です.例えば $[0, 3)$ での累積を計算したければ,$[0, 2)$ と $[2, 3)$ での事前計算の値を使うので, $$ (a_0 \ast a_1) \ast (a_1 \ast a_2) = a_0 \ast a_1 \ast a_2 $$ が要求されます.つまり,任意の $x, y, z \in X$ について, $$ x \ast y \ast y \ast z = x \ast y \ast z $$ が成り立つ必要があります(結合的なので括弧は省略しています).

そして,これが十分であることも確認できます.どの区間での累積を計算するにしても,左端からの長さ2のべき区間と右端からの同様のもので覆って計算するので,左だけ $\ast$ オーバーラップ部分 $\ast$ オーバーラップ部分 $\ast$ 右だけ,の真ん中の重複が消えればよいので上の等式が成り立てば十分なことが分かります.

半群に単位元があれば $x, z$ として単位元を考えると冪等律そのものということになります.逆に,単位元を持たない半群で冪等でもないが上の等式を満たすような本当に要件ギリギリの自然な例は思いつきませんでした.あれば是非教えて下さい.

Sparse Tableのデータ構造としての要請は今述べたとおりなのですが,自然な例が思いつかないのもあり以下では冪等な演算を考えることにします.

次に考えるのは冪等な半群で可換でない例ですが,これも正直面白い例が思いつかず困っていた所,学科同期が定値写像の合成を教えてくれました(言われてみればそうですね).適当に直積を取っていくつかの成分だけ定値写像にして他は恒等写像とかにすると,例えば何かしらの平面とかでの問題とかが解けるのかも,とのことだったので,冪等な半群で可換でない時も使えるというのは覚えておいて損はないかもしれません.

ところがやっぱりあまり潤沢に可換でない例が思いつかないので,以下では可換な演算を考えましょう.だいぶ要件より強い仮定になってしまいましたが,この代数構造には名前がついていてしかもありふれた構造です.半束ですね!今挙げた $min$ や,他にも $gcd$ なども半束になります(もちろんそれぞれの双対な演算も).

半束は任意の2元が下限(上限)を持つ半順序集合に演算 $inf(sup)$ を入れたものと実は同じものということが知られているので,何かしらの順序を考えてその $inf$ や $sup$ を考えたいという時にも使えることがわかります( $gcd$ なんかは整除関係で半順序を入れた所から生じた半束とも見れます).

ひとまずここまでをまとめておくと,Sparse Tableとは 半群 $(X, \ast)$ であって任意の $x, y, z \in X$ について, $$ x \ast y \ast y \ast z = x \ast y \ast z $$ を満たすもの上の列 $(a_i)_{i=0}^{n-1}$ に対して

  • $accumulate(l, r): a_l \ast \cdots \ast a_{r-1}$

を定数時間で計算できるデータ構造となります.実用上では,半束のためのものと思って差し支えないと思われます.

単位元等の付加情報は不要なので,台集合と二項演算の関数オブジェクトをそれぞれテンプレート引数に取るので十分です(正直どちらでも良いと思いますが,内部でエイリアスしたりするのが面倒なので).という訳で以下が実装です.

template<class T, class OP>
class SparseTable {
private:
	OP op;
	const int n;
	vector<int> log2;
	vector<vector<T>> t;

public:
	SparseTable(const vector<T>& v) : n(v.size()), log2(n+1) {
		for (int i = 2; i <= n; ++i) log2[i] = log2[i/2] + 1; // logテーブルの作成
		t.resize(n, vector<T>(log2[n] + 1));
		for (int i = 0; i < n; ++i) t[i][0] = v[i]; // t[i][0]は[i, i+1)での累積なのでv[i]そのもの
		for (int j = 0; j < log2[n]; ++j) {
			int w = 1 << j;
			for (int i = 0; i <= n - (w << 1) ; ++i) {
				T tl = t[i][j], tr = t[i + w][j];
				t[i][j+1] = op(tl, tr);
			}
		}
	}

	T accumulate(int l, int r) {
		int j = log2[r - l];
		return op(t[l][j], t[r - (1 << j)][j]);
	}
};

シンプルですね.ほとんどの事がコンストラクタで行われます.logテーブルは漸化式的に更新すればループを回すだけで,テーブルの更新も幅を固定しつつ内側でiについてループを回せば1つ前(つまり半分)の幅での情報を使って更新が進みます.

RMQがしたければ

struct Min {
	int operator()(int a, int b) { return a < b ? a : b; }
};

vector<int> v;
SparseTable<int, Min> st(v);

みたいなことをすればコンストラクタが $O(n \log n)$ で走って後は累積クエリが定数で呼び放題です.

1つだけ注意ですが,この実装では冪等律を仮定しています. といっても大したものではなくて,累積を計算した区間の幅( $r-l$ )が2の冪になっている時は,$r-2^j=i$ なので $t_{i, j}$ どうしを演算していることになるから,というだけです.冪等律がまずいときは,if (1 << j == r - l) return t[i][j]; なりしておけばよいです.冪等でないがSparse Tableの(最小限の)要件を満たす良い例があればこちらの実装も修正しようと思います.

Share Comments
comments powered by Disqus