差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:segment_tree [2019/11/13] – ikatakos | programming_algorithm:data_structure:segment_tree [2020/12/17] – [双対セグメント木] ikatakos | ||
---|---|---|---|
行 4: | 行 4: | ||
* [[http:// | * [[http:// | ||
- | 区間に対する処理をするときによく使われる。$a_1, | + | * 動画での解説 |
+ | * [[https:// | ||
+ | * [[https:// | ||
- | * 区間和のセグメント木(例) | + | ===== 概要 ===== |
- | * $update(i, | + | |
- | * $query(l, | + | |
- | * 最小値(最大値)のセグメント木(例) | + | |
- | * $update(i, | + | |
- | * $query(l, | + | |
- | バリエーションがある。 | + | 区間に対する集約処理をするときによく使われる。\\ |
+ | $a_1, | ||
- | * 区間更新・一点取得 | + | |
- | * 区間更新・区間取得 | + | * $query(l, |
+ | |||
+ | 「集約」には、身近な例では総和とか最小値とかがあてはまる。 | ||
+ | |||
+ | |||
+ | ==== 管理できるものの条件 ==== | ||
+ | |||
+ | どんな「$a_i$ の型」に対して、どんな「集約操作」を行うか、という(型, | ||
+ | |||
+ | たとえば前者が『整数全体の集合』なら、演算は以下のことが可能である。 | ||
+ | |||
+ | * 区間和、区間積 | ||
+ | * MIN, MAX | ||
+ | * 最小公倍数LCM、最大公約数GCD | ||
+ | * ビット演算 AND、OR、XOR | ||
+ | |||
+ | より厳密に定義しようとすると多少抽象的な話になる。 | ||
+ | |||
+ | [[wpjp> | ||
+ | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せ $(S, \bullet)$ の内、以下の条件を満たすものである。 | ||
+ | |||
+ | * 結合律が成り立つ=計算の順序を入れ替えてもいい | ||
+ | * $(a \bullet b) \bullet c = a \bullet (b \bullet c)$ | ||
+ | * 単位元が存在する | ||
+ | * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する | ||
+ | * $a \bullet e = e \bullet a = a$ | ||
+ | |||
+ | 聞き馴染みが無くとも、足し算とかかけ算とか、割と身近なものでこの性質を満たすものは多い。 | ||
+ | |||
+ | 結合律が必要な理由については、セグメント木は以下のような形でまとまった区間を前計算して、必要な部分を掻い摘まんで集約するので、 | ||
+ | |||
+ | | 1*2*3*4*5*6*7*8 | ||
+ | | 1*2*3*4 | ||
+ | | 1*2 | 3*4 | 5*6 | 7*8 | | ||
+ | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | ||
+ | |||
+ | [ ]: 2~6の集約値を求めるのに参照する箇所 | ||
+ | |||
+ | | | | ||
+ | | | ||
+ | | | ||
+ | | | 2 | | ||
+ | |||
+ | ここでもし '' | ||
+ | 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, | ||
+ | |||
+ | 単位元が存在しない例としては、自然数と足し算があげられる。(足し算は単位元が0だが、自然数に0は含まれない)\\ | ||
+ | 単位元の存在は初期値を埋めておくための実装上の問題かな? | ||
+ | 無理矢理実装できなくも無さそう。 | ||
+ | |||
+ | 例えば単位元が無い自然数上の足し算は、セグメント木で実装できそう。 | ||
+ | (普通、0を使えない言語なんて無いのでこの例は縛りプレイチックになるが) | ||
+ | |||
+ | ===== バリエーション ===== | ||
+ | |||
+ | 構造が比較的単純なため、バリエーションもいくつかある。 | ||
+ | |||
+ | * 一点更新・区間取得(基本) | ||
+ | | ||
+ | * 区間更新・区間取得(遅延セグメント木) | ||
* 多次元化 | * 多次元化 | ||
* 永続化 | * 永続化 | ||
* 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造 | * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造 | ||
- | 逆演算が可能なら、取得できる区間の左端が $a_1$ 固定である [[programming_algorithm: | + | ==== 双対セグメント木 ==== |
- | 例えば区間和なら $a+b=c$ → $c-a=b$ なので、$(区間[l, | + | |
- | 最小値や最大値はこうはいかない。 | + | |
- | =====一点更新・区間取得===== | + | 区間更新・一点取得を行えるデータ構造。できることが通常のセグメント木と逆。 |
+ | |||
+ | 通常のセグメント木は、「更新は、一番下から上に遡上して状態を更新」「取得は、なるべく広い区間をまとめて取得」 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | + | | ||
+ | | | | |+| | | | | | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | * | | ||
+ | | |*| | | | | | | | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | 双対は、操作も逆。 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | + | | ||
+ | | |+| | | | | | | | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | * | | ||
+ | | | | |*| | | | | | ||
+ | |||
+ | === 非可換の場合 === | ||
+ | |||
+ | [[wpjp> | ||
+ | |||
+ | * $(a+b)+c=(a+c)+b$ | ||
+ | |||
+ | セグメント木に載せるものとしては必ずしも成り立つ必要は無いが、もし非可換の場合は順序が保たれるように、演算の左と右に来るものを注意する必要がある。 | ||
+ | |||
+ | セグメント木では注意するくらいで済むが、双対セグメント木では、結構必要な実装が変わってくる。\\ | ||
+ | 具体的に言うと、更新時、更新したいノードより上に溜まっているものがあれば、下まで押し込む必要がある。\\ | ||
+ | 遅延評価セグメント木にも出てくる操作。 | ||
+ | |||
+ | 以下の例を考える。演算として '' | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | 3 | | ||
+ | | | | |1| | | | | [0, 4) に 5 が足された | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | この時、取得するときもこの操作順に合成しなければならない。$1+3+5$ \\ | ||
+ | まぁこの場合はたまたま下から順に合成すれば合うね。 | ||
+ | |||
+ | だが、足される順番を変えてみると(求められる合成順は $5+1+3$)、 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | 3 | | ||
+ | | | | |1| | | | | [2, 4) に 3 が足された | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | このまま下から合成するとさっきと同じ $1+3+5$ となり、可換性がなり立たない場合は間違った答えとなる。 | ||
+ | |||
+ | ここで、$5$ が足された後、より狭い範囲に対して更新操作があったら下まで押し込むようにすると、 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | | | | | | | | | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | | | | ||
+ | | | ||
+ | | 5 | 5 | | ||
+ | | | | | | | | | | | ||
+ | |||
+ | | | | ||
+ | | | ||
+ | | 5 | | ||
+ | | | |5|5| | | | | | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | 5 | | ||
+ | | | |5|6| | | | | | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | 5 | 3 | | ||
+ | | | |5|6| | | | | | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | これで、$i=3$ を取得するときは下から順に合成していけばよくなる。\\ | ||
+ | $6+3$ となるが、$6$ は $5+1$ をこの順に演算した結果なのでこれは $(5+1)+3$ であり、正しく求められる。 | ||
+ | |||
+ | 具体的にどこを押し込むか。\\ | ||
+ | 更新したい区間を $[l, r)$ とすると、$l$ と $r-1$ を表すノードの真上一直線上のノードに溜まっている値は上から順に押し込むとよい。最大 $2 \log{N}$ 個。 | ||
+ | |||
+ | 区間の両端の真上一直線上のノードだけでいいのは、 | ||
+ | 「これより外のノードは、そもそも更新しないので関係ない」 | ||
+ | 「この間に完全に含まれるノードは、必ず一番上のノードで受け止められ、下のノードは更新されないので押し込む必要は無い」と思えばよい。 | ||
+ | |||
+ | ==== 遅延評価セグメント木 ==== | ||
+ | |||
+ | 区間更新・区間取得ができる。上位互換だが、まぁ実装重くなるしバグも埋め込みやすくなるので、過不足の無いデータ構造を選ぶ。 | ||
+ | |||
+ | * [[programming_algorithm: | ||
+ | |||
+ | |||
+ | |||
+ | ==== (番外) Fenwick木 ==== | ||
+ | |||
+ | セグメント木を、機能を限定的にして実装を軽くしたものの1つに、Fenwick木(Binary Indexed Tree)がある。 | ||
+ | |||
+ | * [[programming_algorithm: | ||
+ | |||
+ | /* | ||
+ | * 載せるモノイドは交換律が成り立つ必要がある。$(a+b)+c=(a+c)+b$ | ||
+ | * 取得できる区間の左端が必ず $a_1$ からになる | ||
+ | |||
+ | 逆演算(逆元)があれば、$a[l ... r] = a[1 ... r] - a[1 ... l-1]$ で、1始まりでない区間和も取得できる。 | ||
+ | |||
+ | 逆元があるとは、どんな $S$ 上の要素 $a$ に対しても、それを単位元 $e$ にする $S$ 上の要素 $a^{-1}$ が存在することを指す。 | ||
+ | |||
+ | * $a \bullet a^{-1} = e$ | ||
+ | |||
+ | 例えば足し算なら、正負を反転させれば逆元となる。かけ算なら $\dfrac{1}{a}$ が逆元となる。 | ||
+ | |||
+ | 最小値や最大値には逆元は存在しないので、$a_1$ からの最小値・最大値しか取得できない。 | ||
+ | |||
+ | */ | ||
+ | =====indexの表現方法===== | ||
+ | |||
+ | セグメント木には、2つのindex(っぽい概念)が登場する。 | ||
+ | |||
+ | * (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex | ||
+ | * (2) 二分木を1つの配列で表現する実装において、その配列上のindex | ||
+ | |||
+ | 1 | ||
+ | / | ||
+ | | ||
+ | / \ / \ | ||
+ | 4 5 6 7 | ||
+ | || || || || 対応 | ||
+ | a1 a2 a3 a4 ←(1) | ||
+ | |||
+ | indexは、0始まりか1始まりかを意識する必要がある。 | ||
+ | |||
+ | プログラム全般的には、多くの言語で配列の添字が0-indexなのでそれに倣うことが多いが、 | ||
+ | 特に(2)の二分木の実装では、1-indexにした方が都合が良い。 | ||
+ | |||
+ | 2進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。 | ||
+ | |||
+ | 0001 | ||
+ | / | ||
+ | 0010 | ||
+ | / \ / \ | ||
+ | 0100 0101 0110 0111 | ||
+ | |||
+ | ===== 実装例 ===== | ||
+ | |||
+ | ==== 一点更新・区間取得 ==== | ||
+ | |||
+ | === 基本 | ||
* 2019/11 '' | * 2019/11 '' | ||
+ | |||
+ | ++++ 整数と区間最小値 | | ||
<sxh python> | <sxh python> | ||
行 85: | 行 304: | ||
</ | </ | ||
- | ++++ 再帰を使った書き方(Python, PyPyでは相対的に遅い) | + | ++++ |
+ | |||
+ | === 再帰を使った書き方 | ||
+ | |||
+ | 書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。 | ||
+ | |||
+ | ++++ 整数と区間最小値 | ||
<sxh python> | <sxh python> | ||
行 159: | 行 384: | ||
++++ | ++++ | ||
- | 各値をオブジェクトで持つ場合 | + | === モノイドを注入する === |
- | <sxh python> | + | (単位元、演算)を外部から与えられるようにして柔軟性を持たせた形。ただし実行速度は多少悪くなる。 |
- | class SegmentTree: | + | |
- | """ | + | |
- | 値をObjectで持ち、更新方法を外部から与えられるSegmentTree | + | |
- | | + | |
- | update(i, x): iをxで更新 | + | モノイドは可換でなくてもOK(のはず)。 |
- | get(a, | + | |
- | i,a,b は 0-indexed | + | |
- | """ | + | |
- | | + | ++++ Python3 | |
+ | |||
+ | <sxh python> | ||
+ | class SegmentTreeInjectable: | ||
+ | | ||
""" | """ | ||
:param n: 要素数 | :param n: 要素数 | ||
- | : | + | : |
- | : | + | : |
""" | """ | ||
- | | + | n2 = 1 << |
- | | + | self.offset |
- | while n2 < n: | + | self.data = [e_factory() for _ in range(n2 << 1)] |
- | n2 <<= 1 | + | self.op = operator |
- | self.n2 = n2 | + | self.e = e_factory |
- | self.tree = [init_func() for _ in range(n2 << 1)] | + | |
- | self.ini = init_func | + | @classmethod |
- | self.merge = merge_func | + | def from_array(cls, |
+ | """ | ||
+ | ins = cls(len(arr), | ||
+ | ins.data[ins.offset: | ||
+ | for i in range(ins.offset - 1, 0, -1): | ||
+ | lch = i << 1 | ||
+ | ins.data[i] = operator(ins.data[lch], | ||
+ | return ins | ||
def update(self, | def update(self, | ||
- | | + | |
- | self.merge(self.tree[i], x) | + | # 上書きでなくて加算などで更新したい場合は、get_point() で現在値を取得して呼び出し元で行う |
+ | data = self.data | ||
+ | | ||
+ | i += self.offset | ||
+ | data[i] = x | ||
while i > 1: | while i > 1: | ||
- | self.merge(x, | ||
i >>= 1 | i >>= 1 | ||
- | | + | |
+ | data[i] = op(data[lch], data[lch + 1]) | ||
- | def get(self, | + | def get_point(self, |
- | | + | |
- | q = [(1, 0, self.n2)] | + | |
- | + | ||
- | while q: | + | |
- | k, l, r = q.pop() | + | |
- | + | ||
- | if a <= l and r <= b: | + | |
- | self.merge(result, | + | |
- | continue | + | |
- | + | ||
- | m = (l + r) // 2 | + | |
- | k <<= 1 | + | |
- | if a < m and l < b: | + | |
- | q.append((k, | + | |
- | if a < r and l < m: | + | |
- | q.append((k + 1, m, r)) | + | |
- | + | ||
- | return result | + | |
- | + | ||
- | </ | + | |
- | + | ||
- | =====区間に対する更新と、区間に対するクエリ===== | + | |
- | + | ||
- | 区間足し込みという手法が使える。 | + | |
+ | def get_range(self, | ||
+ | """ | ||
+ | data = self.data | ||
+ | op = self.op | ||
+ | result_l = self.e() | ||
+ | result_r = self.e() | ||
+ | l += self.offset | ||
+ | r += self.offset | ||
+ | while l < r: | ||
+ | if l & 1: | ||
+ | result_l = op(result_l, | ||
+ | l += 1 | ||
+ | if r & 1: | ||
+ | r -= 1 | ||
+ | result_r = op(data[r], result_r) | ||
+ | l >>= 1 | ||
+ | r >>= 1 | ||
+ | return op(result_l, | ||
+ | </ | ||
+ | ++++ | ||