セグメント木

プログラミングコンテストでのデータ構造 (スライド33～)
セグメント木について - beet's soil

概要

区間に対する処理をするときによく使われる。
$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}$ の最小値（最大値）を求める

管理できるものの条件

数学的には、モノイドであればセグメント木で管理することができるとされている。モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。

結合律が成り立つ＝計算の順序を入れ替えてもいい
- $(a \bullet b) \bullet c = a \bullet (b \bullet c)$
単位元が存在する
- $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する
- $a \bullet e = e \bullet a = a$

結合律が成り立たない例としては、実数と冪乗が挙げられる。 $\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$

単位元が存在しない例としては、自然数と足し算があげられる。

ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。
例えば単位元が無い自然数上の足し算は、（初期値などに制約はあるが）セグメント木で実装できる。

バリエーション

構造が比較的単純なため、バリエーションもいくつかある。

一点更新・区間取得（基本）
区間更新・一点取得（双対セグメント木）
区間更新・区間取得（遅延セグメント木）
多次元化
永続化
- 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造

逆元があれば、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にした方が都合が良い。

2進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。

        0001
       /   \
    0010   0011
    / \     / \
0100 0101 0110 0111

実装例

一点更新・区間取得

基本

2019/11 get_min() を、indexとbit演算を使った書き方に変更（速度up）

Python3

再帰を使った書き方

書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。

Python3

        
          
          
              
              class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """
 
    def __init__(self, n):
        """
        :param n: 要素数
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [float('inf')] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1
 
    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_min(a, b, 1, 0, self.n2)
 
    def _get_min(self, a, b, k, l, r):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合はINF
        """
        if r <= a or b <= l:
            return float('inf')
        # [a,b)が完全に[l,r)を包含するならtree[k]で更新
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return min(
            self._get_min(a, b, k << 1, l, m),
            self._get_min(a, b, (k << 1) + 1, m, r)
        )
 
# --------------------------
st = SegTreeMin(30)
st.update(10, 5)
st.update(20, 4)
print(st.get_min(5, 15)) # => 5
print(st.get_min(5, 25)) # => 4
st.update(11, 3)
print(st.get_min(5, 25)) # => 3

            

        
      

モノイドを注入する

（単位元、演算）を外部から与えて柔軟性を持たせた形。ただし実行速度は多少悪くなる。

「既存の値に加える」「既存の値を上書き更新する」の2通りの更新方法が考えられるため、両方できるようにしといた。

Python3

        
          
          
              
              class SegmentTreeInjectable:
    def __init__(self, n, identity_factory, func):
        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
 
    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        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 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):
        """
        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:
            tree[i >> 1] = func(tree[i], tree[i ^ 1])
            i >>= 1
 
    def get_range(self, a, b):
        """
        [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
        r = b + self.offset
        while l < r:
            if r & 1:
                result = func(result, tree[r - 1])
            if l & 1:
                result = func(result, tree[l])
                l += 1
            l >>= 1
            r >>= 1
 
        return result
 
    def get_point(self, i):
        return self.tree[i + self.offset]

            

        
      

区間に対する更新と、区間に対するクエリ

区間足し込みという手法が使える。