文書の過去の版を表示しています。
セグメント木
- プログラミングコンテストでのデータ構造 (スライド33~)
区間に対する処理をするときによく使われる。$a_1,a_2,...,a_n$の配列に対し、以下の2つを処理する。(一点更新区間取得)
- 区間和のセグメント木(例)
- $update(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$ 固定である Binary Indexed Tree が、より高速・実装もシンプルに求められる。 例えば区間和なら $a+b=c$ → $c-a=b$ なので、(区間$[l,r)$の和)$=$(区間$[1,r)$の和)$-$(区間$[1,l)$の和) で求められる。 最小値や最大値はこうはいかない。
一点更新・区間取得
- 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
区間に対する更新と、区間に対するクエリ
区間足し込みという手法が使える。