文書の過去の版を表示しています。
セグメント木
- プログラミングコンテストでのデータ構造 (スライド33～)
区間に対する処理をするときによく使われる。$a_1,a_2,...,a_n$の配列に対し、以下を処理する。（一点更新区間取得）
- 区間和のセグメント木(例)
- $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)$の和) で求められる。 最小値や最大値はこうはいかない。
数学的には、モノイド であればセグメント木で管理することができるとしている。 モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $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
１
/ \
２ ３ ←(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）
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
区間に対する更新と、区間に対するクエリ
区間足し込みという手法が使える。
