文書の過去の版を表示しています。
セグメント木
概要
区間に対する処理をするときによく使われる。
$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$ の組合せの内、以下の条件を満たすものである。
結合律が成り立つ=計算の順序を入れ替えてもいい
単位元が存在する
結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$
単位元が存在しない例としては、自然数と足し算があげられる。
ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。
例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。
バリエーション
構造が比較的単純なため、バリエーションもいくつかある。
一点更新・区間取得(基本)
区間更新・一点取得(双対セグメント木)
区間更新・区間取得(遅延セグメント木)
多次元化
永続化
逆元があれば、Binary Indexed Tree が、より高速で、実装もシンプルに求められる。
逆元があるとは、どんな $S$ 上の要素 $a$ に対しても、それを単位元 $e$ にする $S$ 上の要素 $a^{-1}$ が存在することを指す。
例えば「整数と足し算」というモノイドなら、自身の正負を反転させれば逆元となる。最小値や最大値には存在しない。
indexの表現方法
セグメント木には、2つの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
実装例
一点更新・区間取得
基本
整数と区間最小値
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 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]
区間に対する更新と、区間に対するクエリ