Range Minimum Query (RMQ)
概要
以下のクエリが処理できるセグメント木の実装
-
\(a_i\) の値を \(x\) に更新
-
\(a_l, a_{l+1}, ..., a_{r-1}\) の最小値を求める
セグメント木の最も基本的な形。
特殊ケース高速化
以下のケースについては定数倍高速化ができる。
-
\(a_i\) の値を求める
-
prefix minimum: \(a_0, a_1, ..., a_{r-1}\) の最小値を求める
-
suffix minimum: \(a_l, a_{l+1}, ..., a_{N-1}\) の最小値を求める
prefix/suffixの最小値は、BITベースで計算することで高速化できる。
前計算では、 OEIS - A000265 と OEIS - A322250 をベースに計算する。
計算量
-
更新: \(O(\log N)\)
-
区間最小値: \(O(\log N)\)
実装
再帰的なセグメント木計算は、Pythonでは遅い(場合によってはTLEする)ので、再帰しない形で計算している。
# N: 処理する区間の長さ
N = ...
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
k += N0-1
data[k] = x
while k >= 0:
k = (k - 1) // 2
data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
L = l + N0; R = r + N0
s = INF
while L < R:
if R & 1:
R -= 1
s = min(s, data[R-1])
if L & 1:
s = min(s, data[L-1])
L += 1
L >>= 1; R >>= 1
return s
特殊ケース高速化
前計算として \(O(N)\) の処理を行う。
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# 前計算
I = []; J = []
for x in range(N0, 2*N0+1):
y = (x // (x & -x)) >> 1
I.append((y << 1)-1 if y else 0)
J.append(y << 1)
J.reverse()
# 従来のupdateと同じ
def update(k, x):
k += N0
data[k-1] = x
while k > 1:
k >>= 1
data[k-1] = min(data[2*k-1], data[2*k])
# query [0, r)
def lquery(r):
return min(map(data.__getitem__, __lquery(r)))
def __lquery(r):
while r:
yield I[r]
r -= (r & -r)
# query [l, N0)
def rquery(l):
return min(map(data.__getitem__, __rquery(l)))
def __rquery(l):
r = N0 - l
while r:
yield J[r]
r -= (r & -r)
# query [k, k+1)
def query1(k):
return data[k+N0-1]