日期：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()
C++ 程式碼
線段樹，使用時間約為 28 ms，記憶體約為 25.6 MB，通過測試。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
/* 本題重點，自訂線段樹類別，單點更新，記錄區間和 */
class SegmentTree {
private:
int n;
vector<int> data, tree;
/* 內部遞迴函式 */
void _build(int node, int start, int end) {
// 遞迴出口
if (start == end) {
tree[node] = data[start];
return;
}
// 遞迴，處理左、右半邊
int mid = (end - start) / 2 + start;
_build(2*node + 1, start, mid);
_build(2*node + 2, mid + 1, end);
// 更新 node 對應的區間和
tree[node] = tree[2*node + 1] + tree[2*node + 2];
}
void _update(int node, int start, int end, int target, int val) {
// 遞迴出口
if (start == end) {
tree[node] = val;
data[target] = val;
return;
}
// 遞迴，處理左、右半邊
int mid = (end - start) / 2 + start;
if (target <= mid) { // 在左側
_update(2*node + 1, start, mid, target, val);
} else { // 在右側
_update(2*node + 2, mid + 1, end, target, val);
}
// 更新 node 對應的區間和
tree[node] = tree[2*node + 1] + tree[2*node + 2];
}
int _query(int node, int start, int end, int left, int right) {
// 遞迴出口，[start, end] 與 [left, right] 沒有交集
if (end < left || start > right) {
return 0;
}
// 遞迴出口，[left, right] 包含 [start, end]
if (left <= start && right >= end) {
return tree[node];
}
// 遞迴，處理左、右半邊
int mid = (end - start) / 2 + start;
int lsum = _query(2*node + 1, start, mid, left, right);
int rsum = _query(2*node + 2, mid + 1, end, left, right);
return lsum + rsum;
}
public:
// 建構子，只計算 A[1] ~ A[N] 的最大值、最小值，不要對建 N 之後的值建立線段樹
SegmentTree(const vector<int>& input_data, int target_n) {
data = input_data;
n = target_n;
tree.assign(4*n + 1, 0);
if (n > 0) {
_build(0, 1, n);
}
}
/* 外部呼叫函式 */
void update(int target, int val) {
_update(0, 1, n, target, val);
}
int query(int left, int right) {
return _query(0, 1, n, left, right);
}
};
int main() {
// 讀取測資
int k, m, N, Q;
scanf("%d %d", &k, &m);
vector<int> A (k+1, 0);
for(int i=1; i<=k; i++) {
scanf("%d", &A[i]);
}
scanf("%d %d", &N, &Q);
int limit = max(N, Q);
A.resize(limit + 1); // 調整 A 的長度
// 第1個迴圈，填入 A[k+1] ~ A[limit]
for(int i=k+1; i<=limit; i++) {
A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1;
}
// 第2個迴圈，計算 op, x, y 同時查詢或更新線段樹
SegmentTree st(A, N);
int j = limit;
for(int i=1; i<=Q; i++) {
bool op = A[i] & 1;
int x = (A[i] + A[j]) % N + 1;
if (op) { // 查詢
int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
printf("%d\n", st.query(x, y) % m);
} else { // 更新
int y = ((A[i] << 3) + (A[j] << 5)) % m + 1;
st.update(x, y);
}
j--;
}
return 0;
}
二元索引樹，使用時間約為 14 ms，記憶體約為 12.1 MB，通過測試。
#include <cstdio>
#include <vector>
using namespace std;
class FenwickTree {
private:
int n;
vector<int> arr, tree;
public:
FenwickTree(const vector<int>& A) {
n = (int)A.size() - 1;
arr.assign(n + 1, 0);
tree.assign(n + 1, 0);
for(int i=1; i<=n; i++) {
arr[i] = A[i];
tree[i] = A[i];
}
for(int i=1; i<=n; i++) {
int parent_idx = i + _lowbit(i);
if (parent_idx <= n) {
tree[parent_idx] += tree[i];
}
}
}
int _lowbit(int x) {
return x & (-x);
}
void update(int i, int delta) {
while(i <= n) {
tree[i] += delta;
i += _lowbit(i);
}
}
void update_val(int i, int val) {
int delta = val - arr[i];
arr[i] = val;
update(i, delta);
}
int query(int i) {
int total = 0;
while(i > 0) {
total += tree[i];
i -= _lowbit(i);
}
return total;
}
};
int main() {
// 讀取測資
int k, m, N, Q;
scanf("%d %d", &k, &m);
vector<int> A (k+1, 0);
for(int i=1; i<=k; i++) {
scanf("%d", &A[i]);
}
scanf("%d %d", &N, &Q);
int limit = max(N, Q);
A.resize(limit + 1); // 調整 A 的長度
// 第1個迴圈，填入 A[k+1] ~ A[limit]
for(int i=k+1; i<=limit; i++) {
A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1;
}
// 第2個迴圈，計算 op, x, y 同時查詢或更新線段樹
FenwickTree bit(A);
int j = limit;
for(int i=1; i<=Q; i++) {
bool op = A[i] & 1;
int x = (A[i] + A[j]) % N + 1;
if (op) { // 查詢
int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
int ans = (bit.query(y) - bit.query(x-1)) % m;
printf("%d\n", ans);
} else { // 更新
int y = ((A[i] << 3) + (A[j] << 5)) % m + 1;
bit.update_val(x, y);
}
j--;
}
return 0;
}
沒有留言:
張貼留言