# Segment Tree for RQM class RMQ: N # 完整二元樹的節點數 n # 序列的元素數 = 葉節點數 minv # 儲存最小值的陣列 # 初始化為最低所需的元素數 init(len): n ← 1 while n < len: n ← n*2 # 將葉節點數 n 調整為 2 的冪次方 N ← 2*n - 1 # 調整完整二元樹的節點數 for i ← 0 to N-1: minv[i] ← INF findMin(a, b): return query(a, b, 0, 0, n) query(a, b, k, l, r): if r ≤ a or b ≤ l: res ← INF else if a ≤ l and r ≤ b: res ← minv[k] else: vl ← query(a, b, left(k), l, (l+r)/2) vr ← query(a, b, right(k), (l+r)/2, r) res ← min(vl, vr) return res # 將第 k 個元素改寫為 x update(k, x): k ← k + n - 1 minv[k] ← x while k > 0: k ← parent(k) minv[k] ← min(minv[left(k)], minv[right(k)]) left(k): return 2*k + 1 right(k): return 2*k + 2 parent(k): return (k - 1)/2