beet's soil

競プロのことなど

セグメント木について

注意

間違い、改善点等を見つけたら教えてもらえると助かります。(直すとは言ってない)


問題はここから持ってきました。
https://onlinejudge.u-aizu.ac.jp/#/courses/library/3/DSL/2

はじめに

セグ木ってなに?の人はとりあえず↓
https://www.slideshare.net/iwiwi/ss-3578491


「セグ木とは、前計算と最小限の更新で、区間に対する操作を受け止めることができるデータ構造のこと」
である(と僕は思っている)。

また、セグ木には様々な種類があるが、このブログでは大まかに5つに分けて、
A: 一点更新区間取得:うし木
B: 区間更新一点取得(更新が可換):らて木
C: 区間更新一点取得(上の制限なし):びーと木
D: 区間更新区間取得(更新が可換):Starry Sky木
E: 区間更新区間取得(上の制限なし):遅延セグ木
と呼ぶことにする。(長いので)

簡単のため、添え字は0-indexedとし、区間 [l,r) の半開区間を用い、要素は  N=2^k 個であることとする。
(要素が  2^k 個ではなかったとしても、末尾に適当な値を入れておくことで  2^k 個にできるので)

うし木

まずは一番簡単なうし木から始める。
うし木を書くときに要求される条件は、要素がモノイド(あるいは半群)であることだけだ。

半群やモノイドはあまり聞きなれない言葉かもしれないが、
ある集合  S に対して(例えば  Z とか  R とか)に対して、二項演算  \cdot : S \times S \to S が与えられて、
結合律  a \cdot b \cdot c = (a \cdot b) \cdot c = a \cdot (b \cdot c)
が成り立つ時  (S, \cdot )半群といい、半群  (S, \cdot ) に関して、
ある  e \in S が存在して、任意の  a \in S について   e \cdot a = a \cdot e = a
が成り立つとき、  (S, \cdot )  e 単位元とするモノイドという。

参考:
https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89


日常的な例でいうと、
 (N,+)半群だが、単位元が存在しないためモノイドではない。
 (Z,+) は0を単位元とするモノイドである(したがって半群でもある)。
また、  (R, *) は1を単位元とするモノイドである。

半群からモノイドを生成

ここは別に飛ばしてもいい。

任意の半群について、ある元  e \notin S  S に追加して   S_1 = S \cup \{e\} を作り、
任意の   a \in S_1 について   e \cdot a = a \cdot e = a と定義すると、
 S_1  e 単位元とするモノイドとなる。
言い換えると、適当な単位元を追加することによって、任意の半群をモノイドに埋め込むことができる。

先ほどの例を思い返すと、  (N,+) はモノイドではなかったが、
 N_1 = N \cup \{0\} とすることで、モノイドに埋め込むことができる。
これは絶対に必要なテクニックというわけではないが、覚えておくと実装をサボれることがある。

モノイドの例

ここまで無限集合ばかり例に挙げてきたが、
いくつか有限集合の例も挙げておく。

  •  (\{0\}, *)
  •  (\{1, -1\}, *)
  •  (\{x \mid x \in N , x < 10^9 \}, min)

現実の問題では、  (int, +)  (int, min) などがよく出てくる。

前計算

前計算として、下の図のように、長さが  2^k 区間に対してあらかじめ  \cdot 演算の結果を求めておく。

f:id:beet_aizu:20170910125218j:plain

一段上がるごとに要素数が半分になるので、等比数列の和の公式より、
計算回数は  \sum_{i=0}^{k-1} 2^i = 2^k - 1 = N - 1 となり、  O(N) である。

モノイドのメリット

更新、取得の両方の操作が  O(\log N) で行えることを示していく。
説明の都合上、まずは取得について考える。

 [s, t) という区間は、前計算で求めた区間を高々  O(\log N) 個使って表せる。
例えば  [0,7) なら
f:id:beet_aizu:20170910125233j:plain
 [2,6) なら
f:id:beet_aizu:20170910125244j:plain
 [3,4) なら
f:id:beet_aizu:20170910125253j:plain
のようになる。

うまい説明を思いつかないので証明は省略する。

さて、前置きが長くなってしまったが、
区間  = [s, t)  k 個の区間  [l_0, r_0) \cup [l_1, r_1) \cup \cdots \cup [l_{k-1}, r_{k-1}) に分解し、
 v_{[l, r)} := [l, r) に対して演算を行なった結果と定義すると、
 
v_{[s, t)} = 
a_{s} \cdot a_{s+1} \cdot \cdots \cdot a_{t-1} \\
= (a_{l_0} \cdot a_{l_0+1} \cdot \cdots \cdot a_{r_0-1} ) \cdot (a_{l_1} \cdot a_{l_1+1} \cdot \cdots \cdot a_{r_1-1} ) \cdot \cdots \cdot (a_{l_{k-1}} \cdot a_{l_{k-1}+1} \cdot \cdots \cdot a_{r_{k-1}-1} ) \\
= v_{[l_0, r_0)} \cdot v_{[l_1, r_1)} \cdot \cdots \cdot v_{[l_{k-1}, r_{k-1})}

と表すことができて、下の式の  () の数は高々  O(\log N) 個であり、
 () の中身は前計算であらかじめ求めてあるため、全体として  O(\log N) で演算できる。
ここで上の式から下の式に変形する際に、結合法則を繰り返し用いている。
つまり、  (S, *) がモノイドであることが、このように区間に分けて操作を行うための必要十分条件である。

次に、更新が  O(\log N) で行えることを示す。
 a_i に対して変更を行ったときに影響のある区間 O(\log N) 個である。
よって、愚直に再計算し直すだけでよい。
例えば、下の図は  a_2 を変更を行った場合の更新が必要な要素を表している。
f:id:beet_aizu:20170910131940j:plain

結論として、モノイドのメリットとは

  • 結合法則が成り立つことを利用して、操作を高々 O(\log N ) 個の区間で受け止めることができる。

ことだと言えるだろう。

具体例

イメージしやすいように、具体的な問題を取り上げる。
https://onlinejudge.u-aizu.ac.jp/#/courses/library/3/DSL/2/DSL_2_A

これは一番基本的なうし木の問題であると言える。
制約から、  S = \{ x \mid x \in Z , 0 \le x \le 2^{31} - 1 \} であり、
 min(a, b, c) = min(min(a, b), c) = min(a, min(b, c)) を満たしているから、  (S, min) 半群である。
また、  e=2^{31}-1 とすると、  (S, min)  e 単位元とするモノイドでもある。

したがって、この問題はセグ木を使って解くことができる。
実装例:
https://onlinejudge.u-aizu.ac.jp/#/solutions/problem/DSL_2_A/review/10001872/beet/C++11



クソ長くなったので一回切りまつ。
次回は様々なセグ木の関係性についてまとめようと思っています。