差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:segment_tree [2019/11/13] – ikatakos
+++ programming_algorithm:data_structure:segment_tree [2020/12/24] (現在) – [双対セグメント木] ikatakos
@@ 行 4: / 行 4: @@
   * [[http://beet-aizu.hatenablog.com/entry/2017/09/10/132258|セグメント木について - beet's soil]]
-区間に対する処理をするときによく使われる。$a_1,a_2,...,a_n$の配列に対し、以下を処理する。（一点更新区間取得）
+  * 動画での解説
+    * [[https://www.youtube.com/watch?v=LjhVy1ZJTMc|【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】]]
+    * [[https://www.youtube.com/watch?v=ReGvflPU81c|【木マスター養成講座】4-2. Segment木ってなに〜？なんかうまく区間取ってくる編【競プロかつっぱ】]]
-  * 区間和のセグメント木(例)
+===== 概要 =====
-    * $update(i,x)$ : $a_i$ に $x$ を加算する
-    * $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},...,a_{r-1}$ の合計値を求める
-  * 最小値（最大値）のセグメント木(例)
-    * $update(i,x)$ : $a_i$ を $x$ に上書き更新する
-    * $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},...,a_{r-1}$ の最小値（最大値）を求める
-バリエーションがある。
+区間に対する集約処理をするときによく使われる。\\
+$a_1,a_2,...,a_n$ の配列に対し、以下を処理する。（一点更新・区間取得）
-  * 区間更新・一点取得
+  * $update(i,x)$ : $a_i$ を $x$ で更新する
-  * 区間更新・区間取得
+  * $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},...,a_{r-1}$ の集約値を求める
-  * 多次元化
-  * 永続化
-    * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造
-逆元があれば、取得できる区間の左端が $a_1$ 固定である [[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] が、より高速・実装もシンプルに求められる。
+「集約」には、身近な例では総和とか最小値とかがあてはまる。
-例えば区間和なら $a+b=c$ → $c-a=b$ なので、(区間$[l,r)$の和)$=$(区間$[1,r)$の和)$-$(区間$[1,l)$の和) で求められる。
-最小値や最大値はこうはいかない。
-数学的には、[[wpjp>モノイド]] であればセグメント木で管理することができるとしている。
-モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。
+==== 管理できるものの条件 ====
+どんな「$a_i$ の型」に対して、どんな「集約操作」を行うか、という（型, 操作）の組を、セグメント木は柔軟に変えられる。
+たとえば前者が『整数全体の集合』なら、演算はたとえば以下のことが可能である。
+  * 区間和、区間積
+  * MIN, MAX
+  * 最小公倍数LCM、最大公約数GCD
+  * ビット演算 AND、OR、XOR
+より厳密に定義しようとすると多少抽象的な話になる。
+[[wpjp>モノイド]] であればセグメント木で管理することができるとされている。
+モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せ $(S, \bullet)$ の内、以下の条件を満たすものである。
   * 結合律が成り立つ＝計算の順序を入れ替えてもいい
@@ 行 34: / 行 41: @@
     * $a \bullet e = e \bullet a = a$
+聞き馴染みが無くとも、足し算とかかけ算とか、割と身近なものでこの性質を満たすものは多い。
+結合律が必要な理由については、セグメント木は以下のような形でまとまった区間を前計算して、必要な部分を掻い摘まんで集約するので、
+  |        1*2*3*4*5*6*7*8        |
+  |    1*2*3*4    |    5*6*7*8    |
+  |  1*2  |  3*4  |  5*6  |  7*8  |
+  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+  ↓ 2～6の集約値を求めるのに参照する箇所
+  |                               |
+  |               |               |    2 * (3*4) * (5*6)
+  |       |  3*4  |  5*6  |       |
+  |   | 2 |   |   |   |   |   |   |
+ここでもし ''*'' の演算が結合率を満たさず $(((2*3)*4)*5)*6 \neq 2*(3*4)*(5*6)$ だと困ることが分かる。\\
 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$
-単位元が存在しない例としては、自然数と足し算があげられる。
+単位元が存在しない例としては、自然数と足し算があげられる。（足し算は単位元が0だが、自然数に0は含まれない）\\
+単位元の存在は初期値を埋めておくための実装上の問題。
+だが、実は単位元は $S$ をちょっと拡張することで無理矢理作ることも出来て、
+たとえばタプルにして「自身は単位元であるフラグ」を付け、それがTrueのものとの演算は常にもう片方を返すようにする、などで単位元と振る舞い的に変わらなくなる。\\
+問題を解く上で絶対に $S$ はこの型でないといけない、なんてことは普通無いので、単位元はあまり気にしなくてよい。
+===== バリエーション =====
+構造が比較的単純なため、バリエーションもいくつかある。
+  * 一点更新・区間取得（基本）
+  * 区間更新・一点取得（双対セグメント木）
+  * 区間更新・区間取得（遅延セグメント木）
+  * 多次元化
+  * 永続化
+    * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造
+==== 双対セグメント木 ====
+区間更新・一点取得を行えるデータ構造。できることが通常のセグメント木と逆。
+通常のセグメント木は、「更新は、一番下から上に遡上して状態を更新」「取得は、なるべく広い区間をまとめて取得」
+  【通常のセグメント木】
+  |       +       |    [更新]
+  |   +   |       |    +: i=3 を更新する際に更新が必要なノード
+  |   | + |   |   |
+  | | | |+| | | | |       一番下のノードから、真上のノードを順次更新
+1 2 3 4 5 6 7
+  |               |    [取得]
+  |       |   *   |    *: [1, 8)の集約値を取得するのに参照するノード
+  |   | * |   |   |
+  | |*| | | | | | |       2～3, 4～7 の部分は末端を参照しなくてよい
+1 2 3 4 5 6 7
+双対は、操作も逆。
+  【双対セグメント木】
+  |               |    [更新]
+  |       |   +   |    +: [1, 8) を更新するときに更新するノード
+  |   | + |   |   |
+  | |+| | | | | | |       2～3, 4～7 の部分は末端を更新しなくてよい
+1 2 3 4 5 6 7
+  |       *       |    [取得]
+  |   *   |       |    *: i=3 を取得する際に参照するノード
+  |   | * |   |   |
+  | | | |*| | | | |       一番下のノードから、真上のノードに溜まった更新値を合成していく
+=== 非可換の場合 ===
+[[wpjp>交換法則|可換性]] とは、操作の順番を入れ替えても答えが変わらない性質。足し算やかけ算、MINやMAXなど、これが成り立つものは多い。
+  * $(a+b)+c=(a+c)+b$
+モノイドの要件には入っていないので、セグ木に載せる上で必ずしも成り立っている必要は無い。\\
+ただしもし非可換なら、通常のセグ木の場合、演算の左と右に来るものを取っ替えないように注意する必要がある。
+通常のセグ木では注意するくらいで済むが、双対セグ木では、必要な実装がかなり変わってくる。\\
+具体的に言うと、更新時、更新したいノードより上に溜まっているものがあれば、下まで押し込む必要がある。((この操作は遅延評価セグメント木にも出てくる))
+以下の例を考える。演算として ''+'' を使っているが、今はこれが可換性が成り立たない演算とする。
+  |               |    [更新]
+  |   5   |       |    [0, 4) に 5 が足された
+  |   | 3 |   |   |    [3, 4) に 1 が足された
+  | | | |1| | | | |    [2, 4) に 3 が足された
+1 2 3 4 5 6 7
+この時、取得するときもこの更新順に合成しなければならない。たとえば $i=3$ に対しては $5+1+3$ としなければならない。\\
+しかし、このまま下から合成すると $1+3+5$ となり、間違った答えとなる。
+ここで、$5$ が足された後、より狭い範囲に対して更新操作があったら下まで押し込むようにすると、
+  |               |    [更新]
+  |   5   |       |
+  |   |   |   |   |    [3, 4) に 1 を足したい
+  | | | | | | | | |
+1 2 3 4 5 6 7
+  |               |
+  |       |       |    押し込む
+  | 5 | 5 |   |   |
+  | | | | | | | | |
+  |               |
+  |       |       |    押し込む
+  | 5 |   |   |   |
+  | | |5|5| | | | |
+  |               |    更新したいノードより上のノードに
+  |       |       |    溜まっている値が無くなったところで、
+  | 5 |   |   |   |    改めて [3, 4) に 1 を足す
+  | | |5|6| | | | |
+  |               |
+  |       |       |    [2, 4) に 3 を足す
+  | 5 | 3 |   |   |    下の方に溜まっている値があるのは気にしなくてよい
+  | | |5|6| | | | |
+1 2 3 4 5 6 7
+これで、$i=3$ を取得するときは下から順に合成していけばよくなる。\\
+$6+3$ となるが、$6$ は $5+1$ をこの順に演算した結果なのでこれは $(5+1)+3$ であり、正しく求められている。
+具体的にどこを押し込むか。\\
+更新が必要なノードのうち、左端と右端の、真上一直線上のノードに溜まっている値は上から順に押し込むとよい。最大 $2 \log{N}$ 個。
+  |               v               |
+  |       v       |       v       |    [4, 13) を更新
+  |       |   u   |   u   |   v   |    u: 更新が必要なノード
+  |   |   |   |   |   |   | v |   |    v: 押し込みが必要なノード（上から順に）
+  | | | | | | | | | | | | |u| | | |
+1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+区間の両端の真上一直線上のノードだけでいいのは、
+「これより外のノードは、そもそも更新しないので関係ない」
+「この間に完全に含まれるノードは、必ず一番上のノードで受け止められ、下のノードは更新されないので押し込む必要は無い」と思えばよい。
+==== 遅延評価セグメント木 ====
+区間更新・区間取得ができる。上位互換だが、まぁ実装重くなるしバグも埋め込みやすくなるので、過不足の無いデータ構造を選ぶ。
+  * [[programming_algorithm:data_structure:segment_tree:lazy_segment_tree]]
+==== (番外) Fenwick木 ====
+セグメント木を、機能を限定的にして実装を軽くしたものの1つに、Fenwick木（Binary Indexed Tree）がある。
+  * [[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]]
+/*
+  * 載せるモノイドは交換律が成り立つ必要がある。$(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の表現方法=====
@@ 行 69: / 行 238: @@
 0101 0110 0111
-=====一点更新・区間取得=====
+===== 実装例 =====
+==== 一点更新・区間取得 ====
+=== 基本 ===
   * 2019/11 ''get_min()'' を、indexとbit演算を使った書き方に変更（速度up）
+++++ 整数と区間最小値 |
 <sxh python>
@@ 行 129: / 行 304: @@
 </sxh>
-++++ 再帰を使った書き方（Python, PyPyでは相対的に遅い） |
+++++
+=== 再帰を使った書き方 ===
+書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。
+++++ 整数と区間最小値 |
 <sxh python>
@@ 行 203: / 行 384: @@
 ++++
-各値をオブジェクトで持つ場合
+=== モノイドを注入する ===
-<sxh python>
+（単位元、演算）を外部から与えられるようにして柔軟性を持たせた形。ただし実行速度は多少悪くなる。
-class SegmentTree:
-    """
-    値をObjectで持ち、更新方法を外部から与えられるSegmentTree
-     (汎用性と引き替えに、速度がやや犠牲になる)
-    update(i, x): iをxで更新
+モノイドは可換でなくてもOK（のはず）。
-    get(a,b):     [a, b)を取得
-    i,a,b は 0-indexed
-    """
-    def __init__(self, n, init_func, merge_func):
+++++ Python3 |
+<sxh python>
+class SegmentTreeInjectable:
+    def __init__(self, n, e_factory, operator):
         """
         :param n: 要素数
-        :param init_func: init_func() で初期状態の新しいオブジェクトを返す関数
+        :param e_factory: func() -> S 単位元を生成する関数
-        :param merge_func: merge_func(x, y) でxとyを統合する関数（xを破壊更新する）
+        :param operator: func(S, S) -> S 親ノードが子ノード同士を合成する関数
         """
-        self.n = n
+        n2 = 1 << (n - 1).bit_length()
-        n2 = 1  # nより大きい2の冪数
+        self.offset = n2
-        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, arr, e_factory, operator):
+        """ 既存の配列から生成 """
+        ins = cls(len(arr), e_factory, operator)
+        ins.data[ins.offset:ins.offset + len(arr)] = arr
+        for i in range(ins.offset - 1, 0, -1):
+            lch = i << 1
+            ins.data[i] = operator(ins.data[lch], ins.data[lch + 1])
+        return ins
     def update(self, i, x):
-        i += self.n2
+        """ Aiをxに上書き更新 """
-        self.merge(self.tree[i], x)
+        # 上書きでなくて加算などで更新したい場合は、get_point() で現在値を取得して呼び出し元で行う
+        data = self.data
+        op = self.op
+        i += self.offset
+        data[i] = x
         while i > 1:
-            self.merge(x, self.tree[i ^ 1])
             i >>= 1
-            self.merge(self.tree[i], x)
+            lch = i << 1
+            data[i] = op(data[lch], data[lch + 1])
-    def get(self, a, b):
+    def get_point(self, p):
-        result = self.ini()
+        return self.data[p + self.offset]
-        q = [(1, 0, self.n2)]
-        while q:
-            k, l, r = q.pop()
-            if a <= l and r <= b:
-                self.merge(result, self.tree[k])
-                continue
-            m = (l + r) // 2
-            k <<= 1
-            if a < m and l < b:
-                q.append((k, l, m))
-            if a < r and l < m:
-                q.append((k + 1, m, r))
-        return result
-</sxh>
-=====区間に対する更新と、区間に対するクエリ=====
-区間足し込みという手法が使える。
+    def get_range(self, l, r):
+        """ [l, r) の値を得る """
+        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, data[l])
+                l += 1
+            if r & 1:
+                r -= 1
+                result_r = op(data[r], result_r)
+            l >>= 1
+            r >>= 1
+        return op(result_l, result_r)
+</sxh>
+++++