[[セグメント木]]
現在位置: トップページ » アルゴリズム » データ構造 » セグメント木
文書の表示
管理サイトマップ

差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
programming_algorithm:data_structure:segment_tree [2020/12/13] – ikatakosprogramming_algorithm:data_structure:segment_tree [2020/12/24] (現在) – [双対セグメント木] ikatakos
行 3: 行 3:
   * [[https://www.slideshare.net/iwiwi/ss-3578491|プログラミングコンテストでのデータ構造]] (スライド33～)   * [[https://www.slideshare.net/iwiwi/ss-3578491|プログラミングコンテストでのデータ構造]] (スライド33～)
   * [[http://beet-aizu.hatenablog.com/entry/2017/09/10/132258|セグメント木について - beet's soil]]   * [[http://beet-aizu.hatenablog.com/entry/2017/09/10/132258|セグメント木について - beet's soil]]
 +
 +  * 動画での解説
 +    * [[https://www.youtube.com/watch?v=LjhVy1ZJTMc|【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】]]
 +    * [[https://www.youtube.com/watch?v=ReGvflPU81c|【木マスター養成講座】4-2. Segment木ってなに〜？なんかうまく区間取ってくる編【競プロかつっぱ】]]
  
 ===== 概要 ===== ===== 概要 =====
  
-区間に対する処理をするときによく使われる。\\ +区間に対する集約処理をするときによく使われる。\\ 
-$a_1,a_2,...,a_n$の配列に対し、以下を処理する。（一点更新区間取得）+$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}$ の集約値を求める 
 + 
 +「集約」には、身近な例では総和とか最小値とかがあてはまる。
  
-  * 区間和のセグメント木 
-    * $add(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}$ の最小値（最大値）を求める 
  
 ==== 管理できるものの条件 ==== ==== 管理できるものの条件 ====
  
-数学的には、[[wpjp>モノイド]] であればセグメント木で管理することができるとされている。 +どんな「$a_i$ の型」に対して、どんな「集約操作」を行うか、という（型, 操作）の組を、セグメント木は柔軟に変えられる。 
-モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。+ 
 +たとえば前者が『整数全体の集合』なら、演算はたとえば以下のことが可能である。 
 + 
 +  * 区間和、区間積 
 +  * MIN, MAX 
 +  * 最小公倍数LCM、最大公約数GCD 
 +  * ビット演算 AND、OR、XOR 
 + 
 +より厳密に定義しようとすると多少抽象的な話になる。 
 + 
 +[[wpjp>モノイド]] であればセグメント木で管理することができるとされている。 
 +モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せ $(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    |    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$ 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$
  
-単位元が存在しない例としては、自然数と足し算があげられる。+単位元が存在しない例としては、自然数と足し算があげられる。（足し算は単位元が0だが、自然数に0は含まれない）\\ 
 +単位元の存在は初期値を埋めておくための実装上の問題。 
 + 
 +だが、実は単位元は $S$ をちょっと拡張することで無理矢理作ることも出来て、 
 +たとえばタプルにして「自身は単位元であるフラグ」を付け、それがTrueのものとの演算は常にもう片方を返すようにする、などで単位元と振る舞い的に変わらなくなる。\\ 
 +問題を解く上で絶対に $S$ はこの型でないといけない、なんてことは普通無いので、単位元はあまり気にしなくてよい。
  
-ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。\\ 
-例えば単位元が無い自然数上の足し算は、（初期値などに制約はあるが）セグメント木で実装できる。 
  
 ===== バリエーション ===== ===== バリエーション =====
行 39: 行 73:
  
   * 一点更新・区間取得（基本）   * 一点更新・区間取得（基本）
-  * 区間更新・一点取得+  * 区間更新・一点取得（双対セグメント木）
   * 区間更新・区間取得（遅延セグメント木）   * 区間更新・区間取得（遅延セグメント木）
   * 多次元化   * 多次元化
行 45: 行 79:
     * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造     * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造
  
-逆元があれば、[[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] が、より高速で、実装もシンプルに求められる。\\+==== 双対セグメント木 ==== 
 + 
 +区間更新・一点取得を行えるデータ構造。できることが通常のセグメント木と逆。 
 + 
 +通常のセグメント木は、「更新は、一番下から上に遡上して状態を更新」「取得は、なるべく広い区間をまとめて取得」 
 + 
 +  【通常のセグメント木】 
 +  |       +       |    [更新] 
 +  |   +   |       |    +: i=3 を更新する際に更新が必要なノード 
 +  |   | + |   |   | 
 +  | | | |+| | | | |       一番下のノードから、真上のノードを順次更新 
 +   0 1 2 3 4 5 6 7 
 +   
 +  |               |    [取得] 
 +  |       |   *   |    *: [1, 8)の集約値を取得するのに参照するノード 
 +  |   | * |   |   | 
 +  | |*| | | | | | |       2～3, 4～7 の部分は末端を参照しなくてよい 
 +   0 1 2 3 4 5 6 7 
 + 
 +双対は、操作も逆。 
 + 
 +  【双対セグメント木】 
 +  |               |    [更新] 
 +  |       |   +   |    +: [1, 8) を更新するときに更新するノード 
 +  |   | + |   |   | 
 +  | |+| | | | | | |       2～3, 4～7 の部分は末端を更新しなくてよい 
 +   0 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 が足された 
 +   0 1 2 3 4 5 6 7 
 + 
 +この時、取得するときもこの更新順に合成しなければならない。たとえば $i=3$ に対しては $5+1+3$ としなければならない。\\ 
 +しかし、このまま下から合成すると $1+3+5$ となり、間違った答えとなる。 
 + 
 +ここで、$5$ が足された後、より狭い範囲に対して更新操作があったら下まで押し込むようにすると、 
 + 
 +  |               |    [更新] 
 +  |   5   |       | 
 +  |   |   |   |   |    [3, 4) に 1 を足したい 
 +  | | | | | | | | | 
 +   0 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| | | | | 
 +   0 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| | | | 
 +   0 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}$ が存在することを指す。 逆元があるとは、どんな $S$ 上の要素 $a$ に対しても、それを単位元 $e$ にする $S$ 上の要素 $a^{-1}$ が存在することを指す。
  
   * $a \bullet a^{-1} = e$   * $a \bullet a^{-1} = e$
  
-例えば「整数と足し算」というモノイドなら、自身の正負を反転させれば逆元となる。最小値や最大値には存在しない。+例えば足し算なら、正負を反転させれば逆元となる。かけ算なら $\dfrac{1}{a}$ が逆元となる。
  
 +最小値や最大値には逆元は存在しないので、$a_1$ からの最小値・最大値しか取得できない。
  
 +*/
 =====indexの表現方法===== =====indexの表現方法=====
  
行 89: 行 246:
   * 2019/11 ''get_min()'' を、indexとbit演算を使った書き方に変更（速度up）   * 2019/11 ''get_min()'' を、indexとbit演算を使った書き方に変更（速度up）
  
-++++ Python3 |+++++ 整数と区間最小値 |
  
 <sxh python> <sxh python>
行 153: 行 310:
 書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。 書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。
  
-++++ Python3 |+++++ 整数と区間最小値 |
  
 <sxh python> <sxh python>
行 229: 行 386:
 === モノイドを注入する === === モノイドを注入する ===
  
-（単位元、演算）を外部から与えて柔軟性を持たせた形。ただし実行速度は多少悪くなる。+（単位元、演算）を外部から与えられるようにして柔軟性を持たせた形。ただし実行速度は多少悪くなる。
  
-「既存の値に加える」「既存の値を上書き更新する」の2通りの更新方法が考えられるため、両方できるようにしといた。+モノイドは可換でなくてもOK（のはず）。 
 + 
 +++++ Python3 |
  
 <sxh python> <sxh python>
 class SegmentTreeInjectable: class SegmentTreeInjectable:
-    def __init__(self, n, identity_factory, func):+    def __init__(self, n, e_factory, operator): 
 +        """ 
 +        :param n: 要素数 
 +        :param e_factory: func() -> S 単位元を生成する関数 
 +        :param operator: func(S, S) -> S 親ノードが子ノード同士を合成する関数 
 +        """
         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, arr, identity_factory, func):+    def from_array(cls, arr, e_factory, operator):
         """ 既存の配列から生成 """         """ 既存の配列から生成 """
-        ins = cls(len(arr), identity_factory, func) +        ins = cls(len(arr), e_factory, operator) 
-        ins.tree[ins.offset:ins.offset + len(arr)] = arr+        ins.data[ins.offset:ins.offset + len(arr)] = arr
         for i in range(ins.offset - 1, 0, -1):         for i in range(ins.offset - 1, 0, -1):
-            l = i << 1 +            lch = i << 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], x) 
-        self.__upstream(i) 
  
     def update(self, i, x):     def update(self, i, x):
-        """ +        """ Aiをxに上書き更新 """ 
-        Aiの値をxに更新 +        # 上書きでなくて加算などで更新したい場合は、get_point() で現在値を取得して呼び出し元で行う 
-        :param i: index(0-indexed) +        data = self.data 
-        :param x: update value +        op = self.op
-        """+
         i += self.offset         i += self.offset
-        self.tree[i] = x +        data[i] = x
-        self.__upstream(i) +
- +
-    def __upstream(self, i): +
-        tree = self.tree +
-        func = self.func+
         while i > 1:         while i > 1:
-            tree[i >> 1] = func(tree[i], tree[i ^ 1]) 
             i >>= 1             i >>= 1
 +            lch = i << 1
 +            data[i] = op(data[lch], data[lch + 1])
  
-    def get_range(self, a, b): +    def get_point(self, p): 
-        """ +        return self.data[p + self.offset]
-        [a, b)の値を得る +
-        :param a: index(0-indexed) +
-        :param b: index(0-indexed) +
-        """ +
-        tree = self.tree +
-        func = self.func +
-        result = self.idf()+
  
-        l = a + self.offset +    def get_range(self, l, r): 
-        r = b + self.offset+        """ [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:         while l < r:
-            if r & 1: 
-                result = func(result, tree[r - 1]) 
             if l & 1:             if l & 1:
-                result = func(result, tree[l])+                result_l = op(result_l, data[l])
                 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 result +        return op(result_l, result_r)
- +
-    def get_point(self, i): +
-        return self.tree[i + self.offset]+
  
 </sxh> </sxh>
  
-=====区間に対する更新と、区間に対するクエリ===== +++++
- +
-区間足し込みという手法が使える。 +
- +
- +
- +
- +
  
programming_algorithm/data_structure/segment_tree.txt · 最終更新: 2020/12/24 by ikatakos
文書の表示
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0