セグメント木は区間の集約器
結合法則が成り立つ演算なら、区間を木の節点に分解して集約できます。最小値、最大値、和などに使います。
言語：Python / 計算量：構築 O(N)、操作 O(log N)
考え方
- 演算 op と単位元 e を定義します。
- 葉に値を置き、親は子の集約にします。
- 点更新では根まで再計算。区間質問では O(log N) 個の節点を集めます。
具体例
最小値なら op=min、単位元は∞。[5,2,7,1] の [0,3) の最小値は2です。
実装
a=[5,2,7,1];size=4
t=[float("inf")]*8
t[4:8]=a
for i in range(3,0,-1):t[i]=min(t[2*i],t[2*i+1])
def query(l,r):
l+=size;r+=size;ans=float("inf")
while l<r:
if l&1:ans=min(ans,t[l]);l+=1
if r&1:r-=1;ans=min(ans,t[r])
l//=2;r//=2
return ans
print(query(0,3))注意する条件
引き算は結合法則を満たしません。非可換な演算では左右の集約順序を分けて保持します。
確認問題
min の単位元は？（inf と入力）
解答と理由
inf
min(x,∞)=x なので、空区間の影響をなくせます。
実装課題
講義の配列 [5,2,7,1] の添字1を9に更新して、全体の最小値を出す。入力なし。木を更新してください。
出力:
1参考実装
a=[5,2,7,1];size=4
t=[float("inf")]*8;t[4:8]=a
for i in range(3,0,-1):t[i]=min(t[2*i],t[2*i+1])
p=1+size;t[p]=9
while p>1:
p//=2;t[p]=min(t[2*p],t[2*p+1])
print(t[1])