差分

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

--- programming_algorithm:data_structure:segment_tree [2019/11/13] – [セグメント木] ikatakos
+++ programming_algorithm:data_structure:segment_tree [2020/12/13] – ikatakos
@@ 行 4: / 行 4: @@
   * [[http://beet-aizu.hatenablog.com/entry/2017/09/10/132258|セグメント木について - beet's soil]]
-区間に対する処理をするときによく使われる。$a_1,a_2,...,a_n$の配列に対し、以下を処理する。（一点更新区間取得）
+===== 概要 =====
-  * 区間和のセグメント木(例)
+区間に対する処理をするときによく使われる。\\
-    * $update(i,x)$ : $a_i$ に $x$ を加算する
+$a_1,a_2,...,a_n$の配列に対し、以下を処理する。（一点更新区間取得）
+  * 区間和のセグメント木
+    * $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}$ の最小値（最大値）を求める
-バリエーションがある。
+==== 管理できるものの条件 ====
-  * 区間更新・一点取得
-  * 区間更新・区間取得
-  * 多次元化
-  * 永続化
-    * 更新を加えたときに、後から遡って「時刻 $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>モノイド]] であればセグメント木で管理することができるとしている。
+数学的には、[[wpjp>モノイド]] であればセグメント木で管理することができるとされている。
-モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\dot$ の組合せの内、以下の条件を満たすものである。
+モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。
   * 結合律が成り立つ＝計算の順序を入れ替えてもいい
-    * $(a \dot b) \dot c = a \dot (b \dot c)$
+    * $(a \bullet b) \bullet c = a \bullet (b \bullet c)$
   * 単位元が存在する
     * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する
-    * $a \dot e = e \dot a = a$
+    * $a \bullet e = e \bullet a = a$
 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$
@@ 行 38: / 行 31: @@
 単位元が存在しない例としては、自然数と足し算があげられる。
-ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。
+ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。\\
 例えば単位元が無い自然数上の足し算は、（初期値などに制約はあるが）セグメント木で実装できる。
-=====一点更新・区間取得=====
+===== バリエーション =====
+構造が比較的単純なため、バリエーションもいくつかある。
+  * 一点更新・区間取得（基本）
+  * 区間更新・一点取得
+  * 区間更新・区間取得（遅延セグメント木）
+  * 多次元化
+  * 永続化
+    * 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造
+逆元があれば、[[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] が、より高速で、実装もシンプルに求められる。\\
+逆元があるとは、どんな $S$ 上の要素 $a$ に対しても、それを単位元 $e$ にする $S$ 上の要素 $a^{-1}$ が存在することを指す。
+  * $a \bullet a^{-1} = e$
+例えば「整数と足し算」というモノイドなら、自身の正負を反転させれば逆元となる。最小値や最大値には存在しない。
+=====indexの表現方法=====
+セグメント木には、2つのindex（っぽい概念）が登場する。
+  * (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex
+  * (2) 二分木を1つの配列で表現する実装において、その配列上のindex
+        １
+       /  \
+     ２    ３     ←(2)
+    / \    / \
+  ４  ５  ６  ７
+  ||  ||  ||  ||    対応
+  a1  a2  a3  a4  ←(1)
+indexは、0始まりか1始まりかを意識する必要がある。
+プログラム全般的には、多くの言語で配列の添字が0-indexなのでそれに倣うことが多いが、
+特に(2)の二分木の実装では、1-indexにした方が都合が良い。
+進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。
+
+         /   \
+   0011
+      / \     / \
+0101 0110 0111
+===== 実装例 =====
+==== 一点更新・区間取得 ====
+=== 基本 ===
   * 2019/11 ''get_min()'' を、indexとbit演算を使った書き方に変更（速度up）
+++++ Python3 |
 <sxh python>
@@ 行 101: / 行 147: @@
 </sxh>
-++++ 再帰を使った書き方（Python, PyPyでは相対的に遅い） |
+++++
+=== 再帰を使った書き方 ===
+書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。
+++++ Python3 |
 <sxh python>
@@ 行 175: / 行 227: @@
 ++++
-各値をオブジェクトで持つ場合
+=== モノイドを注入する ===
+（単位元、演算）を外部から与えて柔軟性を持たせた形。ただし実行速度は多少悪くなる。
+「既存の値に加える」「既存の値を上書き更新する」の2通りの更新方法が考えられるため、両方できるようにしといた。
 <sxh python>
-class SegmentTree:
+class SegmentTreeInjectable:
-    """
+    def __init__(self, n, identity_factory, func):
-    値をObjectで持ち、更新方法を外部から与えられるSegmentTree
+        n2 = 1 << (n - 1).bit_length()
-     (汎用性と引き替えに、速度がやや犠牲になる)
+        self.offset = n2
+        self.tree = [identity_factory() for _ in range(n2 << 1)]
+        self.func = func
+        self.idf = identity_factory
-    update(i, x): iをxで更新
+    @classmethod
-    get(a,b):     [a, b)を取得
+    def from_array(cls, arr, identity_factory, func):
-    i,a,b は 0-indexed
+        """ 既存の配列から生成 """
-    """
+        ins = cls(len(arr), identity_factory, func)
+        ins.tree[ins.offset:ins.offset + len(arr)] = arr
+        for i in range(ins.offset - 1, 0, -1):
+            l = i << 1
+            r = l + 1
+            ins.tree[i] = func(ins.tree[l], ins.tree[r])
+        return ins
-    def __init__(self, n, init_func, merge_func):
+    def add(self, i, x):
         """
-        :param n: 要素数
+        Aiにxを加算
-        :param init_func: init_func() で初期状態の新しいオブジェクトを返す関数
+        :param i: index (0-indexed)
-        :param merge_func: merge_func(x, y) でxとyを統合する関数（xを破壊更新する）
+        :param x: add value
         """
-        self.n = n
+        i += self.offset
-        n2 = 1  # nより大きい2の冪数
+        self.tree[i] = self.func(self.tree[i], x)
-        while n2 < n:
+        self.__upstream(i)
-            n2 <<= 1
-        self.n2 = n2
-        self.tree = [init_func() for _ in range(n2 << 1)]
-        self.ini = init_func
-        self.merge = merge_func
     def update(self, i, x):
-        i += self.n2
+        """
-        self.merge(self.tree[i], x)
+        Aiの値をxに更新
+        :param i: index(0-indexed)
+        :param x: update value
+        """
+        i += self.offset
+        self.tree[i] = x
+        self.__upstream(i)
+    def __upstream(self, i):
+        tree = self.tree
+        func = self.func
         while i > 1:
-            self.merge(x, self.tree[i ^ 1])
+            tree[i >> 1] = func(tree[i], tree[i ^ 1])
             i >>= 1
-            self.merge(self.tree[i], x)
-    def get(self, a, b):
+    def get_range(self, a, b):
-        result = self.ini()
+        """
-        q = [(1, 0, self.n2)]
+        [a, b)の値を得る
+        :param a: index(0-indexed)
-        while q:
+        :param b: index(0-indexed)
-            k, l, r = q.pop()
+        """
+        tree = self.tree
-            if a <= l and r <= b:
+        func = self.func
-                self.merge(result, self.tree[k])
+        result = self.idf()
-                continue
+        l = a + self.offset
-            m = (l + r) // 2
+        r = b + self.offset
-            k <<= 1
+        while l < r:
-            if a < m and l < b:
+            if r & 1:
-                q.append((k, l, m))
+                result = func(result, tree[r - 1])
-            if a < r and l < m:
+            if l & 1:
-                q.append((k + 1, m, r))
+                result = func(result, tree[l])
+                l += 1
+            l >>= 1
+            r >>= 1
         return result
+    def get_point(self, i):
+        return self.tree[i + self.offset]
 </sxh>