差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:segment_tree [2020/12/13] – [一点更新・区間取得] ikatakos | programming_algorithm:data_structure:segment_tree [2020/12/24] – [双対セグメント木] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
* [[https:// | * [[https:// | ||
* [[http:// | * [[http:// | ||
+ | |||
+ | * 動画での解説 | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
===== 概要 ===== | ===== 概要 ===== | ||
- | 区間に対する処理をするときによく使われる。\\ | + | 区間に対する集約処理をするときによく使われる。\\ |
- | $a_1, | + | $a_1, |
+ | |||
+ | * $update(i, | ||
+ | * $query(l, | ||
+ | |||
+ | 「集約」には、身近な例では総和とか最小値とかがあてはまる。 | ||
- | * 区間和のセグメント木 | ||
- | * $add(i,x)$ : $a_i$ に $x$ を加算する | ||
- | * $query(l, | ||
- | * 最小値(最大値)のセグメント木 | ||
- | * $update(i, | ||
- | * $query(l, | ||
==== 管理できるものの条件 ==== | ==== 管理できるものの条件 ==== | ||
- | 数学的には、[[wpjp> | + | どんな「$a_i$ の型」に対して、どんな「集約操作」を行うか、という(型, |
- | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。 | + | |
+ | たとえば前者が『整数全体の集合』なら、演算はたとえば以下のことが可能である。 | ||
+ | |||
+ | * 区間和、区間積 | ||
+ | * MIN, MAX | ||
+ | * 最小公倍数LCM、最大公約数GCD | ||
+ | * ビット演算 AND、OR、XOR | ||
+ | |||
+ | より厳密に定義しようとすると多少抽象的な話になる。 | ||
+ | |||
+ | [[wpjp> | ||
+ | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せ | ||
* 結合律が成り立つ=計算の順序を入れ替えてもいい | * 結合律が成り立つ=計算の順序を入れ替えてもいい | ||
行 27: | 行 41: | ||
* $a \bullet e = e \bullet a = a$ | * $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, | 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, | ||
- | 単位元が存在しない例としては、自然数と足し算があげられる。 | + | 単位元が存在しない例としては、自然数と足し算があげられる。(足し算は単位元が0だが、自然数に0は含まれない)\\ |
+ | 単位元の存在は初期値を埋めておくための実装上の問題。 | ||
+ | |||
+ | だが、実は単位元は $S$ をちょっと拡張することで無理矢理作ることも出来て、 | ||
+ | たとえばタプルにして「自身は単位元であるフラグ」を付け、それがTrueのものとの演算は常にもう片方を返すようにする、などで単位元と振る舞い的に変わらなくなる。\\ | ||
+ | 問題を解く上で絶対に $S$ はこの型でないといけない、なんてことは普通無いので、単位元はあまり気にしなくてよい。 | ||
- | ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。\\ | ||
- | 例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。 | ||
===== バリエーション ===== | ===== バリエーション ===== | ||
行 45: | 行 79: | ||
* 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造 | * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造 | ||
- | 逆元があれば、[[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] が、より高速で、実装もシンプルに求められる。\\ | + | ==== 双対セグメント木 ==== |
+ | |||
+ | 区間更新・一点取得を行えるデータ構造。できることが通常のセグメント木と逆。 | ||
+ | |||
+ | 通常のセグメント木は、「更新は、一番下から上に遡上して状態を更新」「取得は、なるべく広い区間をまとめて取得」 | ||
+ | |||
+ | 【通常のセグメント木】 | ||
+ | | | ||
+ | | | ||
+ | | | + | | ||
+ | | | | |+| | | | | | ||
+ | 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| | | | | [2, 4) に 3 が足された | ||
+ | 0 1 2 3 4 5 6 7 | ||
+ | |||
+ | この時、取得するときもこの更新順に合成しなければならない。つまり、$5+1+3$ としなければならない。\\ | ||
+ | しかし、このまま下から合成すると $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$ であり、正しく求められている。 | ||
+ | |||
+ | 具体的にどこを押し込むか。\\ | ||
+ | 更新が必要なノードのうち、左端と右端の、真上一直線上のノードに溜まっている値は上から順に押し込むとよい。最大 $2 \log{N}$ 個。 | ||
+ | |||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | | | | | | | | | | | |u| | | | | ||
+ | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | ||
+ | |||
+ | 区間の両端の真上一直線上のノードだけでいいのは、 | ||
+ | 「これより外のノードは、そもそも更新しないので関係ない」 | ||
+ | 「この間に完全に含まれるノードは、必ず一番上のノードで受け止められ、下のノードは更新されないので押し込む必要は無い」と思えばよい。 | ||
+ | |||
+ | ==== 遅延評価セグメント木 ==== | ||
+ | |||
+ | 区間更新・区間取得ができる。上位互換だが、まぁ実装重くなるしバグも埋め込みやすくなるので、過不足の無いデータ構造を選ぶ。 | ||
+ | |||
+ | * [[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}$ が存在することを指す。 | 逆元があるとは、どんな $S$ 上の要素 $a$ に対しても、それを単位元 $e$ にする $S$ 上の要素 $a^{-1}$ が存在することを指す。 | ||
* $a \bullet a^{-1} = e$ | * $a \bullet a^{-1} = e$ | ||
- | 例えば「整数と足し算」というモノイドなら、自身の正負を反転させれば逆元となる。最小値や最大値には存在しない。 | + | 例えば足し算なら、正負を反転させれば逆元となる。かけ算なら $\dfrac{1}{a}$ が逆元となる。 |
+ | 最小値や最大値には逆元は存在しないので、$a_1$ からの最小値・最大値しか取得できない。 | ||
+ | */ | ||
=====indexの表現方法===== | =====indexの表現方法===== | ||
行 229: | 行 386: | ||
=== モノイドを注入する === | === モノイドを注入する === | ||
- | (単位元、演算)を外部から与えて柔軟性を持たせた形。ただし実行速度は多少悪くなる。 | + | (単位元、演算)を外部から与えられるようにして柔軟性を持たせた形。ただし実行速度は多少悪くなる。 |
- | 「既存の値に加える」「既存の値を上書き更新する」の2通りの更新方法が考えられるため、両方できるようにしといた。 | + | モノイドは可換でなくてもOK(のはず)。 |
++++ Python3 | | ++++ Python3 | | ||
行 237: | 行 394: | ||
<sxh python> | <sxh python> | ||
class SegmentTreeInjectable: | class SegmentTreeInjectable: | ||
- | def __init__(self, | + | def __init__(self, |
+ | """ | ||
+ | :param n: 要素数 | ||
+ | :param e_factory: | ||
+ | | ||
+ | """ | ||
n2 = 1 << (n - 1).bit_length() | n2 = 1 << (n - 1).bit_length() | ||
self.offset = n2 | self.offset = n2 | ||
- | self.tree = [identity_factory() for _ in range(n2 << 1)] | + | self.data = [e_factory() for _ in range(n2 << 1)] |
- | self.func = func | + | self.op = operator |
- | self.idf = identity_factory | + | self.e = e_factory |
@classmethod | @classmethod | ||
- | def from_array(cls, | + | def from_array(cls, |
""" | """ | ||
- | ins = cls(len(arr), | + | ins = cls(len(arr), |
- | ins.tree[ins.offset: | + | ins.data[ins.offset: |
for i in range(ins.offset - 1, 0, -1): | for i in range(ins.offset - 1, 0, -1): | ||
- | | + | |
- | r = l + 1 | + | ins.data[i] = operator(ins.data[lch], ins.data[lch + 1]) |
- | ins.tree[i] = func(ins.tree[l], ins.tree[r]) | + | |
return ins | return ins | ||
- | |||
- | def add(self, i, x): | ||
- | """ | ||
- | Aiにxを加算 | ||
- | :param i: index (0-indexed) | ||
- | :param x: add value | ||
- | """ | ||
- | i += self.offset | ||
- | self.tree[i] = self.func(self.tree[i], | ||
- | self.__upstream(i) | ||
def update(self, | def update(self, | ||
- | """ | + | """ |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
i += self.offset | i += self.offset | ||
- | | + | |
- | self.__upstream(i) | + | |
- | + | ||
- | def __upstream(self, | + | |
- | tree = self.tree | + | |
- | func = self.func | + | |
while i > 1: | while i > 1: | ||
- | tree[i >> 1] = func(tree[i], | ||
i >>= 1 | i >>= 1 | ||
+ | lch = i << 1 | ||
+ | data[i] = op(data[lch], | ||
- | def get_range(self, | + | def get_point(self, |
- | | + | |
- | [a, b)の値を得る | + | |
- | :param a: index(0-indexed) | + | |
- | :param b: index(0-indexed) | + | |
- | """ | + | |
- | tree = self.tree | + | |
- | func = self.func | + | |
- | result = self.idf() | + | |
- | | + | def get_range(self, |
- | r = b + self.offset | + | """ |
+ | data = self.data | ||
+ | op = self.op | ||
+ | result_l = self.e() | ||
+ | result_r = self.e() | ||
+ | |||
+ | l += self.offset | ||
+ | r += self.offset | ||
while l < r: | while l < r: | ||
- | if r & 1: | ||
- | result = func(result, | ||
if l & 1: | if l & 1: | ||
- | | + | |
l += 1 | l += 1 | ||
+ | if r & 1: | ||
+ | r -= 1 | ||
+ | result_r = op(data[r], result_r) | ||
l >>= 1 | l >>= 1 | ||
r >>= 1 | r >>= 1 | ||
- | return | + | return |
- | + | ||
- | def get_point(self, i): | + | |
- | return self.tree[i + self.offset] | + | |
</ | </ | ||
++++ | ++++ | ||
- | =====区間に対する更新と、区間に対するクエリ===== | ||
- | |||
- | 区間足し込みという手法が使える。 | ||
- | |||
- | |||
- | |||
- | |||
- | |||