題意#
給定一個長度為 \( n \) 的陣列，並且有 \( m \) 次操作。
操作分為兩種：
- 將陣列在索引 \( k \) 的值更新為 \( u \)。
- 查詢區間 \( [a, b] \) 內所有元素的總和。
思路#
相較於靜態的區間和，這題因為包含了單點修改的操作，
如果每次修改都重新計算前綴和，時間複雜度會高達 \( O(n) \)，絕對會讓程式超時（TLE）。
這類「單點修改、區間查詢」的經典題型，
最適合使用**樹狀陣列（Binary Indexed Tree, BIT 或 Fenwick Tree）**來處理。
樹狀陣列能讓我們將單點修改與區間查詢的時間複雜度雙雙降至 \( O(\log n) \)。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
vector<int> v, bit;
int n, m;
// 樹狀陣列：單點修改（將 val 加到索引 idx）
void upd(int idx, int val) {
for (; idx <= n; idx += idx&-idx) bit[idx] += val;
}
// 樹狀陣列：查詢區間 [a, b] 的總和
int get(int a, int b) {
int sa = 0, sb = 0; a--;
for (; a > 0; a -= a&-a) sa += bit[a];
for (; b > 0; b -= b&-b) sb += bit[b];
return sb-sa;
}
signed main() { WA();
cin >> n >> m;
v.resize(n+1); bit.resize(n+1, 0);
// 初始化陣列與樹狀陣列
for (int i = 1; i <= n; i++) {
cin >> v[i];
upd(i, v[i]);
}
while (m--) {
int c, a, b;
cin >> c >> a >> b;
if (c == 1) {
// 單點修改：先扣去原有的值，再補上新值
upd(a, -v[a]);
v[a] = b;
upd(a, b);
}
else cout << get(a, b) << '\n'; // 區間總和查詢
}
}
