日期：2026年5月22日
ZeroJudge 題目連結：e409. Segment Tree 練習
解題想法
這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，遞迴版的線段樹與二元索引樹都太慢，後來是用非遞迴版的線段樹才過關。
Python 程式碼
遞迴版線段樹，從測資 #4 開始超時。
import sys
sys.setrecursionlimit(10000)
# --- 本題重點，自訂線段樹類別，單點更新，記錄區間最大值、最小值 ---
class SegmentTree:
def __init__(self, data, n):
self.data = data
self.n = n
self.imax = [0] * (4*self.n + 1)
self.imin = [0] * (4*self.n + 1)
if self.n > 0:
self._build(0, 1, self.n) # 題目的 A 是 1-index
# --- 內部遞迴函式 ---
def _build(self, node, start, end):
# 遞迴出口
if start == end:
self.imax[node] = self.data[start]
self.imin[node] = self.data[start]
return
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
self._build(2*node + 1, start, mid)
self._build(2*node + 2, mid + 1, end)
# 更新 node 對應的最大值、最小值
self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
def _update(self, node, start, end, target, val):
# 遞迴出口
if start == end:
self.imax[node] = val
self.imin[node] = val
self.data[target] = val
return
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
if target <= mid: # 在左側
self._update(2*node + 1, start, mid, target, val)
else: # 在右側
self._update(2*node + 2, mid + 1, end, target, val)
# 更新 node 對應的最大值、最小值
self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
def _query(self, node, start, end, left, right):
# 遞迴出口，[start, end] 與 [left, right] 沒有交集
if end < left or start > right:
return (-2000000000, 2000000000)
# 遞迴出口，[left, right] 包含 [start, end]
if left <= start and right >= end:
return (self.imax[node], self.imin[node])
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
L = self._query(2*node + 1, start, mid, left, right)
R = self._query(2*node + 2, mid + 1, end, left, right)
return (max(L[0], R[0]), min(L[1], R[1]))
# --- 外部呼叫函式 ---
def update(self, target, val):
self._update(0, 1, self.n, target, val)
def query(self, left, right):
res = self._query(0, 1, self.n, left, right)
return res[0] - res[1]
# --- 主要的解題過程 ---
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
MaxN, MaxQ = 1000005, 100005
k = int(data[ptr])
m = int(data[ptr+1])
ptr += 2
A = [0]*MaxN
for i in range(1, k+1):
A[i] = int(data[ptr])
ptr += 1
N = int(data[ptr])
Q = int(data[ptr+1])
ptr += 2
C = [False]*MaxQ
X = [0]*MaxQ
Y = [0]*MaxQ
# 題目中給定的産生資料函式
def gen_dat():
# 第一個迴圈
limit = max(Q, N)
i = k+1
while i <= limit:
A[i] = (A[i-2]*97 + A[i-1]*3) % m + 1
i += 1
# 第二個迴圈
i = 1
j = limit
while i <= Q:
C[i] = A[i] & 1
X[i] = (A[i] + A[j]) % N + 1
if C[i]: Y[i] = X[i]+ ( (A[i] << 3) + (A[j] << 5) + m ) % (N - X[i] + 1)
else: Y[i] = ((A[i] << 3) + (A[j] << 5)) % m + 1
i += 1
j -= 1
# 呼叫 gen_dat() 産生 A 的完整內容
gen_dat()
#print(A[:26]) # 印出前 26 項檢查內容
# 讀取 operations 並輸出答案
st = SegmentTree(A, N)
for i in range(1, Q+1):
op, x, y = C[i], X[i], Y[i]
if op == 0:
st.update(x, y)
elif op == 1:
result.append(f"{st.query(x, y):d}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
