日期：2026年5月21日
ZeroJudge 題目連結：e406. Binary Indexed Tree 練習題
解題想法
這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，則會因為線段樹需要遞迴很多次，速度太慢，無法過關。
Python 程式碼
二元索引樹，使用時間約為 1.1 s，記憶體約為 73 MB，通過測試。
class FenwickTree:
def __init__(self, A):
self.n = len(A) - 1
self.A = A[:]
self.tree = A[:]
for i in range(1, self.n + 1):
parent_idx = i + self._lowbit(i)
if parent_idx <= self.n:
self.tree[parent_idx] += self.tree[i]
def _lowbit(self, x):
return x & (-x)
def update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += self._lowbit(i)
def update_val(self, i, val):
delta = val - self.A[i]
self.A[i] = val
self.update(i, delta)
def query(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= self._lowbit(i)
return total
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
k = int(data[ptr])
m = int(data[ptr+1])
ptr += 2
A = [0] + list(map(int, data[ptr:ptr+k]))
ptr += k
N = int(data[ptr])
Q = int(data[ptr+1])
ptr += 2
limit = max(N, Q)
A += [0] * (limit - k + 1) # 調整 A 的長度
# 第1個迴圈，填入 A[k+1] ~ A[limit]
for i in range(k+1, limit + 1):
A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1
# 第2個迴圈，計算 op, x, y 同時查詢或更新
bit = FenwickTree(A)
j = limit
for i in range(1, Q+1):
op = A[i] & 1
x = (A[i] + A[j]) % N + 1
if op: # 查詢
y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1)
ans = (bit.query(y) - bit.query(x-1)) % m
result.append(f"{ans:d}\n")
else: # 更新
y = ((A[i] << 3) + (A[j] << 5)) % m + 1
bit.update_val(x, y)
j -= 1
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
