文書の過去の版を表示しています。
セグメント木
- プログラミングコンテストでのデータ構造 (スライド33~)
概要
区間に対する処理をするときによく使われる。
$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
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)
再帰を使った書き方
書き方がシンプルになり人によってはアレンジしやすくなる一方、Python、PyPyでは相対的に遅くなるため非推奨。
モノイドを注入する
(単位元、演算)を外部から与えて柔軟性を持たせた形。ただし実行速度は多少悪くなる。
「既存の値に加える」「既存の値を上書き更新する」の2通りの更新方法が考えられるため、両方できるようにしといた。
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]
区間に対する更新と、区間に対するクエリ
区間足し込みという手法が使える。