セグメント木について

注意

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

はじめに

先にこっちを見て　
beet-aizu.hatenablog.com

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

はじめに

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

遅延伝播セグメント木についてはこちら↓
beet-aizu.hatenablog.com

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

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

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

うし木

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

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

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

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

半群からモノイドを生成

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

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

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

モノイドの例

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

• ({0},∗)$(\{0\},\ast )$
• ({1,−1},∗)$(\{1,-1\},\ast )$
• ({x∣x∈N,x<109},min)$(\{x\mid x\in N,x<{10}^9\},min)$

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

前計算

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

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

モノイドのメリット

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

[s,t)$[s,t)$ という区間は、前計算で求めた区間を高々 O(logN)$O(\log N)$ 個使って表せる。
例えば [0,7)$[0,7)$ なら

[2,6)$[2,6)$ なら

[3,4)$[3,4)$ なら

のようになる。

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

さて、前置きが長くなってしまったが、
区間 =[s,t)$=[s,t)$ を k$k$ 個の区間 [l0,r0)∪[l1,r1)∪⋯∪[lk−1,rk−1)$[l_0,r_0)\cup [l_1,r_1)\cup \cdots \cup [l_{k-1},r_{k-1})$ に分解し、
v[l,r):=[l,r)$v_{[l,r)}:=[l,r)$ に対して演算を行なった結果と定義すると、
v[s,t)=as⋅as+1⋅⋯⋅at−1=(al0⋅al0+1⋅⋯⋅ar0−1)⋅(al1⋅al1+1⋅⋯⋅ar1−1)⋅⋯⋅(alk−1⋅alk−1+1⋅⋯⋅ark−1−1)=v[l0,r0)⋅v[l1,r1)⋅⋯⋅v[lk−1,rk−1)$$\begin{gathered} 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})} \end{gathered}$$

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

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

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

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

ことだと言えるだろう。

具体例

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

これは一番基本的なうし木の問題であると言える。
制約から、 S={x∣x∈Z,0≤x≤231−1}$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))$min(a,b,c)=min(min(a,b),c)=min(a,min(b,c))$ を満たしているから、 (S,min)$(S,min)$ は半群である。
また、 e=231−1$e=2^{31}-1$ とすると、 (S,min)$(S,min)$ は e$e$ を単位元とするモノイドでもある。

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

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