# Segment Tree for RSM class RSQ: N # 完整二元樹的節點數 n # 序列的元素數 = 葉節點數 sum # 儲存總和的陣列 # 初始化為最低所需之元素數 init(len): n ← 1 while n < len: n ← n*2 # 將葉節點數 n 調整為初始元素的兩倍 N ← 2*n - 1 # 調整完整二元樹的節點數 for i ← 0 to N-1: sum[i] ← 0 findSum(a, b): return query(a, b, 0, 0, n) query(a, b, k, l, r): if r ≤ a or b ≤ l: res ← 0 else if a ≤ l and r ≤ b: res ← sum[k] else: vl ← query(a, b, left(k), l, (l+r)/2) vr ← query(a, b, right(k), (l+r)/2, r) res ← vl + vr return res # 將第 k 個元素加上 x update(k, x): k ← k + n - 1 sum[k] ← sum[k] + x while k > 0: k ← parent(k) sum[k] ← sum[left(k)] + sum[right(k)] left(k): return 2*k + 1 right(k): return 2*k + 2 parent(k): return (k - 1)/2