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

この記事はIS17er Advent Calendar 2016の12日目の記事です.

この記事では,列とその連続部分列に対するクエリを扱う基本的なデータ構造についての代数的なお話をします.具体的には,Segment Tree, Binary Indexd TreeとSparse Tableを扱います.この並びでお気づきの方もいらっしゃるとは思いますが,要は僕がプログラミングコンテストチャンレジブックを読み進めながら思ったことをまとめた記事になっています.

そもそもこの記事を書くまで知らなかったようなデータ構造についても扱っており,素人の学習日記のような側面もあり簡潔さに欠けるので,是非データ構造と代数構造 - koba-e964の日記も読まれることをおすすめします(ちなみに,Advent CalendarのタイトルのIS17erとは東京大学理学部情報科学科2017年度進学生のことを指すのですが,こちらの記事は学科の先輩が書かれたものです).

ブログ自体書くのがはじめてで,どんな方に読んで頂いてるのかよく分からないので念のための注意(言い訳)ですが,僕はプログラミング自体大学で初めて触れたド素人なので,競技プログラミング系の記事と言い切ってしまうとその手の人が期待する水準には恐らく及びません(今は友人にICPCに誘われて慌てて上の本で勉強中です),が,代数的に汎用的だが高速に動作するC++コードも目玉の一つなので,是非斜め読みしていってください.

全体は前編と後編からなり,この記事は 前編 です.

注意

前編,後編を通していくつか嘘が残っています.また書くと言って書いてない部分もあります.極力懐疑的に読んでください.まとまった時間が取れたら一通り整理する予定です.

前提

データ構造

はじめに挙げたこの記事で扱う3つのデータ構造の基礎については既知とします(Segment Treeについての話題が約半分を占めるので後の2つは知らなくてもあまり差し支えありません).Segment TreeやSparseTableでRange Minimum Queryが,Segment TreeやBinary Indexd TreeでRange Sum Queryが解けるという事についての一通りの理解があれば十分だと思います.

ネット上にある教育的な文献については詳しくないのですが,Segment Treeについてはプログラミングコンテストでのデータ構造が,Binary Indexd TreeについてはこちらのBinary Indexed Tree のはなしが参考になると思います.

代数

代数も基礎的な部分は記事を読み進めるにあたって理解している必要があります.といっても,”二項演算についての抽象化は見通しが良く嬉しい”ぐらいの部分しか使わないので,代数学の著名な結果等を理解している必要は全くなくて,代数構造の標準的な抽象化と分類のマナーを知っていれば大丈夫です.適宜Google先生に質問すれば大丈夫ではないかなと思います.

具体的には,二項演算付き集合のいくつかのクラス(半群,モノイド,群,半束)及びモノイドの作用などを主に扱います.

凡例

$n = \{0, 1, \ldots, n-1\}$ から $X$ への写像 $a$ の事を $X$ 上の(長さ $n$ の)列と呼んで,$a(i) = a_i$ と書いて $a = (a_0, \ldots, a_{n-1})$ や $(a_i)_{i=0}^{n-1}$ と書きます.これら全体の集合は $X$ の $n$ 個の直積とおなじものです( $A$ から $B$ への写像全体を $B^A$ と書いたことを思い出すとどちらも $X^n$ ということになります).

列 $(a_i)_{i=0}^{n-1}$ に対して,その連続部分列 $(a_i)_{i=l}^{r-1} = (a_l, \ldots, a_{r-1}) \in X^{r-l}$ を $a[l, r)$ や単に $[l, r)$ で表します.この表記と併せて列の連続部分列のことを区間と呼びます.

また,$X$ を定義域とする写像 $f$ があるとき,$x = (x_0, \ldots , x_{n-1}) \in X^n$ に対して $f(x)$ で $(f(x_0), \ldots , f(x_{n-1}))$ を表すことにします.

コードは全てC++で書かれています.全体を通してusing namespace std;を予めしておいたものとして省略しています.また,ヘッダは適宜必要なものをincludeしてあるものとします.

Segment Tree

はじめに

ここでは

  • 1点に対する更新と区間での演算の累積を扱えるもの
  • 区間に対する一様な更新を扱えるもの.
  • 区間に対する一様な更新と区間での演算の累積を扱えるもの

の3種類のSegment Treeについて扱います.

本当は一番上のものだけを扱う予定(というよりそれしか知らない)だったのですが,後述のいきさつでこのようになりました.理解したばかりのものについても書いているので,おかしな点があれば是非教えて下さい.

Segment Treeの実装はEfficient and easy segment treesを大いに参考にしました.メインテーマの代数的抽象化とは別に,区間に対するクエリの関数の非再帰化可能性を疑って,あれこれ考えながら調べていたら辿りついた記事です.この記事が非常にわかりやすく,せっかくなので上に挙げた3つのタイプ全てを扱うことになりました.よってここでも概ねこの記事の流れに沿って書かれています(実装と流れをベースにするというだけで,記事の趣旨は直交していると思います).

1点更新,区間累積

RMQやRSQを扱う最も基本的なSegTreeを考えます.各ノードは列の区間に対応しており,前者なら各ノードは左の子と右の子の $min$ を,後者ならそれらの $+$ を保持していて,$[l, r)$ に対するクエリというのは極力大きい区間で受け止めることによって $O(\log n)$ で達成されていました.

$min$ や $+$ はいずれも二項演算であったことを思い出すと,各ノードは2つの子の演算結果を保持していて,$[l, r)$ に対するクエリというのは演算を区間上で繰り返し計算したもの(累積)を問われていると考えることができます.

では二項演算なら何でもいいかというとそうではなくて,そもそも $[l, r)$ での演算の累積が区間を定めるだけで意味を持たなければいけません.例えば $-$ という演算の累積を考えても,$3-2-1$ を $(3-2)-1$ として計算するか $3-(2-1)$ として計算するかで値が変わってしまい,$3-2-1$ というのが意味を持ちません(といっても引き算は普通左結合で,括弧なしでも前者として解釈されます.でもこの左結合だという了解がないとやはりまずいです).つまり,ある意味大前提として演算は結合的であることが要求されます.

逆に,演算が結合的なら,内部の二分木に先程述べたような構造をもたせればRMQやRSQと同様の事が実現できるのが分かります.結局,このタイプの基本的なSegTreeというのは以下をサポートするデータ構造だということが分かります.

半群 $(X, \ast)$ 上の列 $(a_i)_{i=0}^{n-1}$ に対して,

  • $set(i, x)$ : $a_i \leftarrow x$
  • $accumulate(l, r)$ : $a_l \ast \ldots \ast a_{r-1}$

といっても,実のところ サイズの異なる行列が並んでいて掛け算をしたい時のように,$a_i$ と $a_{i+1}$ の間に演算が定まっていてこの列上で見ると結合的であれば十分です.要は列上で機能してさえいれば元の代数構造における演算の全域性は不要ということです.更に言えば,欲しいものがまさに $a_l \ast \ldots \ast a_{r-1}$ をSegTreeが内部的に評価する順序のものピッタリという(特殊な)場合ではもちろん結合性すら不要です.しかしこれらまで考慮した一般化はかえってtrivialなものになりかねないので,この記事では例外として扱うことにします.

ところで,半群は簡単にモノイドにできます.単位元を持たない半群 $(X, \ast)$ に対して,$e$ を $X$ のどの元とも異なる対象として,$X’=X \cup \{e\}$ および $\ast’: X’ \times X’ \rightarrow X’$ を $\ast$ の真の拡大であって任意の $x \in X’$ に対して $e \ast’ x = x \ast’ e = x$ を満たすものと定めれば,$(X’, \ast’)$ はモノイドになります.

例えば,半群 $(\mathbf R, min)$ に対して $\infty$ なる元を $\mathbf R$ に加えて妥当な意味になるように演算を拡大すれば $\infty$ を単位元とするモノイドにできる.という感じです.

実装上では,例えば型の表現できる値の中で使わないものがあればそれを単位元にしてしまうという方法があります.型Tの中で使わない値unusedがあったとすると

T op(T a, T b); // 半群の演算

T op_m(T a, T b) {
	if (a == unused) return b;
	if (b == unused) return a;
	return op(a, b);
}

のようにunusedが単位元として働くよう演算をラップすれば良いです(非負整数しか使わないなら-1を単位元にしてしまう等).といっても,多くの場合型Tの中に妥当な単位元の表現があることが多いと思います.int上のRMQならINT_MAXを単位元とすればいいし,gcdなら,”任意の素数の倍数である必要があるから発散しちゃう…?”と思ってもよくよく考えれば0が妥当な単位元です.

実装の観点上便利なので以下半群は全て必要なら適当な単位元を付加してモノイドとして扱ったものとします

ここまででひとまず任意のモノイド上の列を扱うものだと一般化できたので実装しましょう.

/*
struct Monoid {
	using T = _underlying_set_; // モノイドの台集合の型
	T operator()(const T& a, const T& b) { return _a_op_b_; } // 二項演算
	static constexpr T identity() { return _identity_element_; } // 単位元
};
*/

template<class Monoid>
class SegTree {
private:
	using T = typename Monoid::T; // 台集合の型をエイリアス
	Monoid op; // 演算の関数オブジェクト
	const int n; // 列の長さ
	vector<T> t; // 内部二分木

	void prop_to(int i) { t[i] = op(t[2*i], t[2*i+1]); } // ノードiに伝播

public:
	SegTree(int n) : n(n), t(2*n, op.identity()) {} // デフォルトでは内部は単位元で埋めておく
	SegTree(const vector<T>& v) : n(v.size()), t(2*n) { // 初期値を各点更新はO(nlogn),はじめにまとめてコピーしてまとめて伝播するとO(n)
		copy(begin(v), end(v), begin(t) + n);
		for (int i = n-1; i > 0; --i) prop_to(i);
	}

	void set(int i, const T& x) { // 列のi番目をxに
		t[i += n] = x; // 列のi番目に対応する葉のノードのインデックスはi + n
		while (i >>= 1) prop_to(i); // 根まで更新を登りつつ伝播
	}

	T get(int i) { return t[i + n]; } // 列のi番目を返す

	T accumulate(int l, int r) {
		T accl = op.identity(), accr = op.identity();
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) accl = op(accl, t[l++]);
			if (r & 1) accr = op(t[r-1], accr);
		}
		return op(accl, accr);
	}
};


主要な部分を順に解説していきます.任意のモノイドに対して抽象化をしたのでまずモノイドの構造体を作りましょう.必要な情報はもちろん台集合と演算とその単位元の3つなので冒頭でコメントアウトしてある通りに書きます.例えばint上でRMQをしたいなら

struct RMQ {
	using T = int;
	T operator()(const T& a, const T& b) { return a < b ? a : b; }
	static constexpr T identity() { return INT_MAX; }
};

という感じに書きます.operator()をオーバーロードしたものは関数オブジェクトと言って,はやいらしいです(関数ポインタを渡すのでは関数の中身が実行時まで見えないのでインライン展開などができないが,これだとできたりして良いらしい).sortで昇順にしたい時とかpriority_queueで大きい順に取り出したい時とかに渡すgreater<T>とかがそれです.

抽象化したコードは普通はオーバーヘッドで遅くなりますが,この実装は抽象化した分をほぼ全てコンパイル時計算に詰め込んである(はず)のでかなり高速に動作します(後で速さ比べします).

区間での演算の累積を計算するメンバ関数ははじめに述べたように非再帰で書かれています.

T accumulate(int l, int r) {
	T accl = op.identity(), accr = op.identity();
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) accl = op(accl, t[l++]);
		if (r & 1) accr = op(t[r-1], accr);
	}
	return op(accl, accr);
}

詳細な動作原理は先述の記事を参照してほしいのですが,何をやっているか簡単に説明すると,$[l, r)$ を $[l, \infty)$ と $(-\infty, r)$ の共通部分のように見て,$l$ 側はどんどん右へ, $r$ 側はどんどん左へある意味独立に進めていきます.今 $l$ 側が左の子になっているノードを見ている時は,ここでわざわざ何かしなくても親も同等以上の情報を覚えているので何もせず上がります..右の子を見ているときは,そのまま親に上がってしまうと兄弟(左の子)の情報が親に混ざっていて邪魔なのでここで累積に値を積むしかなくて,それをした後は $l$ を1つ右にズラせば左の子なのでそのまま1段上がれます.$r$ 側も同様です.

この実装では,計算量は正確には $\Theta(\log(r-l))$ になっています.再帰版の実装では,区間の幅によらず内部の持つ区間から微妙にはみ出ると葉まで下る必要があったり,逆に $[0, n)$ なんかは根ノードで直ちに終了できたりとまちまちなので比べて真に性能が良いとは言えませんが,そもそも非再帰化しただけでもかなりの高速化になります.

累積をacclとaccrの2つに分けているのは演算が可換でない時用です.実際両端から内側に向かって値が積まれていくので演算の順序の保存にはこうする必要があります.最後にacclとaccrをくっつけて終わりです.

また,せっかくのライブラリなので随所で申し訳程度の最適化をしています.元の実装からの改善点のほか主要なものをいくつか挙げると

  • 極力bit演算を使う
  • ただし配列の添字の時だけはアドレッシングモード(最近習いました)に埋め込んでくれるみたいで2*i+1と書く方が若干はやいのでそっちを採用
  • 演算をするとコンディションレジスタにフラグが立ってそのまま条件分岐に利用できる(最近習いました)ので while(i > 1) { i >>= 1; ...} でなくて while (i >>= 1) {...}にしている
  • もとはif (r & 1) accr = op(t[--r], accr);となっていたがrが奇数の時の条件付きだから2で割った結果はわざわざrを1減らして書き戻さなくても同じでr-1で十分

などなどです.再帰展開に比べると本当に微々たるものですが,他にもあればぜひぜひ教えてください.

また,RSQ等で $a_i$ に $x$ を加えたい,みたいな時はありますが,後述の区間に対する更新と違って1点更新のやり方は実際いくつ混在していても問題ない( $x$ かける,$n$ 乗する,絶対値を取る…)ので一般化という意味では対応できません.代わりにgetを用意してあるのでset(i, get(i)+x)みたいにしましょう.

先述の通り汎用的ですが非常に高速に動作します.再帰版はサイズが2のべきでないと動かない && 定数倍遅すぎた(一応ベタ書きに比べて遅くないということを言いたい)ので唯一これだけ測定に用いたideoneのtime limitを超えないギリギリのデータ数にしていますが,その他は要素数 $10^7$ の列を簡単のため $a_i = i$ としてRMQを計算させて,$accumulate(l, r) = l$ かどうかで動作をチェックしています.

測定結果からも分かるように,汎用的であるにもかかわらず再帰版より高速に動作(もちろん非再帰にしてるのが最も大きいですが,定数倍で2倍以上は違うことになります)して,かつ抽象化した分のオーバーヘッドはほとんどないことが分かります.

学科同期からコメントをもらったのでここに追記しておきますが,一概に非再帰版が速いと言うのは少し違って,再帰版は並列化可能性の点で非再帰の実装より優れているということでした.確かに並列化をすると容易に逆転しそうですね.

せっかくなのでいくつか例を挙げてこの節を終わりとします.

  • RSQ(テンプレート)
template<class T_>
struct RSQ<T_> {
	using T = T_;
	T operator() (const T& a, const T& b) { return a + b; }
	static constexpr T identity() { return T(0); };
};
  • 1次関数と合成(モノイドときたら写像と合成というイメージがあるので,簡潔な有限の表現を持っていて合成に関して閉じている簡単な例として)
using L = pair<int, int>; // (a, b) : ax+b
struct Lcmp {
	using T = L;
	T operator()(const T& a, const T& b) { return L(a.first * b.first, a.first * b.second + a.second); } // a(cx+d)+b = (ac)x+(ad+b)
	static constexpr T identity() { return L(1, 0); } // id(x)=x
};

SegTreeからモノイドの実装を分離して抽象化しておくのは本当に見通しが良い上に再利用性が高くて最高ですね!

区間更新SegTree

今度は連続部分列に対する更新を考えます.$[l, r)$ を全部 $x$ にしたい,もしくは $x$ を足したい/掛けたい,などです.足していく例で考えると,これは区間に対する加算をできるだけ大きい区間で受け止めて覚えておくと実現できます(最初のタイプの区間での累積を扱う関数と全く同様のループを回して,今度は拾うべきノードにストックしていきます).$a_i$ の値を知りたければ,$i$ を含むような区間を全部見てそれらの区間に一様に足された値を全部足していけば $O(\log n)$ で実現できます(結局,根まで親を辿り続ければ良いです).

void add(int l, int r, int x) {
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) t[l++] += x;
		if (r & 1) t[r-1] += x;
	}
}

int get(int i) {
	int s = t[i += n];
	while (i >>= 1) s += t[i];
	return s;
}

では,整数の列があったら,整数上の足し算,整数上の掛け算のような整数上のモノイドを成す演算を区間に対して一様に実行できるというのが(後は型を一般化すれば)このSegTreeの十分な一般化になっているかというと,まだそうではありません.例えば,整数上の列の区間に対して,一様に1次関数 $f(x)=ax+b$ を適用したい,というようなクエリにもこのSegTreeは答えることができます.各ノードが担当している区間に対して一様に適用された1次関数を覚えておけば良いです.既に区間に $f$ が適用されていて,更に $g$ を適用したいというクエリが来た時はその区間が覚えている関数を $g \circ f$ に更新すれば良いです.

言い換えると,ある種の変換の区間に対して一様な適用を扱えるが,複数の変換を1つにまとめられる(30度回転の後に50度回転という2つの変換は80度回転という変換にまとめられる,等)必要があるということです.ここまできたらもう大丈夫だと思いますが,このSegTreeは列の区間に対するモノイドの一様な作用を扱えます.結合則の要求は各点に作用したモノイドの元の列がそこの先祖のノードにいくつかに分断されて保持されていることから,また単位元は同様に便利なので付加しておきます.

ここで納得した方,睡眠は大事です. 夜中3時に寝ぼけながらこのあたりを書いていたのですが,朝起きて(起床が苦手なのでホントはお昼でした)嘘を書いていたことに気づきました.

例えば $[0, 4)$ に $f_1$ を,続けて $[0, 2)$ に $f_2$ を,再び $[0, 4)$ に $f_3$ を適用したとすると,$[0, 4)$ に対応するノードが覚えているのは $f_3 \circ f_1$ で $[0, 2)$ に対応するノードが覚えているのは $f_2$ です.ところが0番目の値は結局 $f_3 \circ f_2 \circ f_1$ を適用されたはずなので,上の実装と同じ方法ではどう合成の順番を工夫しても親ノードが受け止めて覚えてる分からは復元できません( $f_2$ が割って入れない).

要は,上の実装をモノイドの作用にそのまま抽象化するなら,作用素モノイドの演算の可換律 が必要だということです.上で挙げた1次関数の合成なんて全然可換じゃないのでダメダメですね.

ではどうするかというと,$[0, 2)$ にモノイドの元を積む前に $[0, 4)$ が覚えてる分を予め下ろしてくればよいです.既にご存知の方にしか伝わらない言い方ですが,3つ目の区間に対する累積と更新の両方をサポートするタイプで使われるLazy Propagationというテクニックのある意味半分を実装すれば良いことになります(実はこの部分を書いてる段階では遅延SegTreeをまだあんまり理解していなかったのですが,こうやって切り分けるとすっきり理解できました).

ある所に作用素モノイドの値を積みたい時はそのノードの先祖が覚えてる分は全て先に下ろしてこないといけないので,更新クエリではまずはじめに $[l, r)$ を更新する時にループを回して値を積んでいきたいノード達の先祖全てが保持している作用を,予め下ろしてくる必要があります.ところがこのノードの集合は実は $l$ に対応する葉と $r-1$ に対応する葉の先祖のノードの集合の和に等しいことが簡単に分かります.

実際 $l$ 側では右側の子のみを拾って右にずれていくので,今拾おうとしているノードに対して,1回前に拾われたノードは必ず自分の兄弟(左側)の部分木にあります(拾うまでは左側を見ては無視して登るを繰り返すだけなので).すると今拾われたノードの親は1つ前に拾ったノードの先祖になっているので,これを繰り返し考えれば最初に扱う $l$ に対応する葉ノードの先祖が全てをカバーしていることが分かります.$r-1$ 側も同様です.

よって $l$ に対応するノードと $r-1$ に対応するノードから根までのパスを,根から順に下におろしていけば良いことが分かります.再帰関数で書くと簡単ですが非再帰化も難しくないので非再帰で書きましょう.以下のコードで根から順に辿れるので,これを用います(このへんの話は実装の話で,先述の参考記事にもほぼ同内容のことが 画像つきで あるのでやはりそちらも参照してください).

int h; // 内部二分木の高さ gccなら__lg(n)等で簡単に計算できる

void prop_to(int i) {
	i += n;
	for (int s = (i >> h ? h : h-1); s > 0; --s) {
		// prop from (i >> s)
	}
}

完全二分木でない時はi >> (h-1)が根になるノードもあるので初期値は場合分けしています.

改めてまとめると,このタイプのSegTreeは以下のようなクエリに対応しています(作用は $M$ の元を1つ決める度に $X \rightarrow X$ が定まっているものと考えて冒頭の凡例で述べた記法を用いています).

集合 $X$ 上の元の列 $(a_i)_{i=0}^{n-1}$ とモノイド $(M, \ast)$ があって $X$ への $M$-作用 $.: M \times X \rightarrow X$ が定まっているとき,

  • $act(l, r, m) : a[l, r) \leftarrow m.a[l, r)$
  • $get(i) : a_i$

以下はその実装です.ふつう作用といえば左作用として書くことが多いようなのでそれにならっていますが,モノイドの演算の向きには注意してください(モノイドは先述のインターフェースを持つものとします). 関数適用は右からが良いという人は全部逆にしたほうが良いかもしれません(本当は僕もそっちの方が好きです).メインは最初に書いたようなループで作用素モノイドの値を積んでいくことと,積む前に作用の順番を壊さないように先に上に留まってる作用は必要な所まで下ろしてくるという2つで,後は補助関数だったりオマケだったりするのであまり気にしなくて大丈夫です.

/*
struct M_act {
	using T = _operand_set_; // 作用される側の集合の型
	using Monoid = _operator_monoid_; // 作用素モノイド
	T operator()(const Monoid::T& m, const T& a) { return _m_act_a_; } // 作用演算
};
*/
template <class M_act>
class SegTree {
private:
	using T = typename M_act::T; // 作用される側の集合の型をエイリアス
	using M = typename M_act::Monoid::T; // 作用素モノイドの台集合をエイリアス
	M_act action; // 作用演算子
	typename M_act::Monoid op; // 作用素モノイドの演算子
	const int n, h; // 列の長さ,木の高さ
	vector<T> t; // 列の値
	vector<M> a; // 区間で保留されている一様な作用,葉の分はそのまま適用してしまえばいいので不要で長さはnで十分
	bool has_lazy; // まだ葉まで降ろされてない作用があるかどうかのフラグ

	void act(int i, const M& m) { // ノードiに作用
		if (i < n) a[i] = op(m, a[i]); // 内部ノードなら作用と作用を作用素モノイドの演算でまとめる
		else t[i -= n] = action(m, t[i]); // 葉なら作用は適用してしまう
	}

	void prop_from(int i) { // ノードiの作用を子に下ろす
		act(i << 1, a[i]);
		act(i << 1 | 1, a[i]);
		a[i] = op.identity();
	}

	void prop_to(int i) { // i番目の値への作用を全て葉まで下ろしてくる
		i += n;
		for (int s = (i >> h ? h : h-1), p; s > 0; --s) prop_from(i >> s);
	}

public:
	SegTree(int n, const T& x) : n(n), h(__lg(n)), t(n, x), a(n, op.identity()), has_lazy() {} // 一様にxで埋めるコンストラクタ
	SegTree(const vector<T>& v) : n(v.size()), h(__lg(n)), t(v), a(n, op.identity()), has_lazy() {} // 初期値をvectorで渡すコンストラクタ

	void act(int l, int r, const M& m) { // [l, r)にmを作用させる
		prop_to(l);
		prop_to(r-1);
		l += n, r += n;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) act(l++, m);
			if (r & 1) act(r-1, m);
		}
		has_lazy = true;
	}

	void prop() { // 根から順に全ての作用を葉まで下ろす
		for (int i = 1; i < n; ++i) prop_from(i);
		has_lazy = false;
	}

	void set(int i, const T& x) { // i番目の値の点更新
		prop_to(i);
		t[i] = x;
	}

	T get(int i) { // i番目の値の取得
		if (!has_lazy) return t[i]; // 保留してる作用がないならそのまま返す
		T ret = t[i];
		i += n;
		while (i >>= 1) ret = action(a[i], ret); // そうでないなら根まで登って上のノードが溜め込んでる作用を被っていく
		return ret;
	}
};

例えば,1次関数の区間への一様な適用を扱いたいなら

struct L_act {
	using T = int;
	using Monoid = Lcmp;
	T operator()(const Monoid::T& m, const T& a) { return m.first * a + m.second; }
}

みたいに作用される集合と作用素モノイドとその具体的な作用演算を書いて終わりです(Lcmpは上で挙げたものです). 他にも,区間に一様にassignしたい時は定値写像と合成が成すモノイドを作用させればよいですね.今挙げた一次関数のようなアフィン変換から見るとその特殊な場合とも考えられます.といっても,一様なassignは適用順に従う優先度を付け加えて優先度が一番高いもののみをgetで拾うという方法でもできます.これもある意味(優先度,assignする値)のペアを優先度で比較して大きい方を取るという演算が入ったモノイドの作用を考えているとも見れます(maxは可換なので,はじめの区間addのように作用の順番を気にしないで済むため実装をサボれます).

最初のタイプと違って,今回のコードは抽象化のためにコードがそれなりに長くなってる節が否めないので,もっとスマートな実装があれば是非教えてください.

Share Comments
comments powered by Disqus