セグメント木

区間に対する処理をするときによく使われる。$a_1,a_2,\ldots,a_n$の配列に対し、以下を処理する。(一点更新区間取得)

  • 区間和のセグメント木(例)
    • $update(i,x)$ : $a_i$ に $x$ を加算する
    • $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},\ldots,a_{r-1}$ の合計値を求める
  • 最小値(最大値)のセグメント木(例)
    • $update(i,x)$ : $a_i$ を $x$ に上書き更新する
    • $query(l,r)$ : 区間 $[l,r) = a_l,a_{l+1},\ldots,a_{r-1}$ の最小値(最大値)を求める

バリエーションがある。

  • 区間更新・一点取得
  • 区間更新・区間取得
  • 多次元化
  • 永続化
    • 更新を加えたときに、後から遡って「時刻 $t$ での状態」を復元できる構造

逆元があれば、取得できる区間の左端が $a_1$ 固定である Binary Indexed Tree が、より高速・実装もシンプルに求められる。 例えば区間和なら $a+b=c$ → $c-a=b$ なので、(区間$[l,r)$の和)$=$(区間$[1,r)$の和)$-$(区間$[1,l)$の和) で求められる。 最小値や最大値はこうはいかない。

数学的には、モノイド であればセグメント木で管理することができるとしている。 モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $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$

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

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

indexの表現方法

セグメント木には、2つのindex(っぽい概念)が登場する。

  • (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex
  • (2) 二分木を1つの配列で表現する実装において、その配列上のindex
      1
     /  \
   2    3     ←(2)
  / \    / \
4  5  6  7
||  ||  ||  ||    対応
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)

class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値(入りうる要素より十分に大きな数)
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result

再帰を使った書き方(Python, PyPyでは相対的に遅い)

各値をオブジェクトで持つ場合

class SegmentTree:
    """
    値をObjectで持ち、更新方法を外部から与えられるSegmentTree
     (汎用性と引き替えに、速度がやや犠牲になる)

    update(i, x): iをxで更新
    get(a,b):     [a, b)を取得
    i,a,b は 0-indexed
    """

    def __init__(self, n, init_func, merge_func):
        """
        :param n: 要素数
        :param init_func: init_func() で初期状態の新しいオブジェクトを返す関数
        :param merge_func: merge_func(x, y) でxとyを統合する関数(xを破壊更新する)
        """
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            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)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.merge(self.tree[i], x)

    def get(self, a, b):
        result = self.ini()
        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

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

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

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/data_structure/segment_tree.txt · 最終更新: 2019/11/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0