树状数组 (BIT)CSP-S

💡 核心思想

树状数组（Binary Indexed Tree, BIT）用于高效处理前缀查询和单点修改。核心是 lowbit 运算（取最低位1代表的值），用 $O(\log n)$ 完成单点修改和前缀求和。常用于求逆序对、动态前缀和等。

🎯 直觉理解

想象你要维护一组数的"从开头到第 k 个的和"。朴素做法每次 $O(k)$。树状数组就像把前缀分成若干段预先算好的区间，查询时只需要合并 $\log n$ 段。就像你有不同面额的硬币，用最少的硬币凑出任意金额。

📝 算法流程

1. lowbit(x) = x & (-x)
2. 修改：从位置 i 开始，i += lowbit(i) 一直往上
3. 查询前缀和：从位置 i 开始，i -= lowbit(i) 一直往下
4. 可扩展为区间修改+区间查询

$$lowbit(x) = x \& (-x)$$

$$tree[i] = \sum_{j=i-lowbit(i)+1}^{i} a[j]$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int n;
long long tree[500005];
int lowbit(int x) { return x & (-x); }
void add(int i, long long v) { for (; i <= n; i += lowbit(i)) tree[i] += v; }
long long sum(int i) { long long s = 0; for (; i > 0; i -= lowbit(i)) s += tree[i]; return s; }
int main() {
    int m; cin >> n >> m;
    for (int i = 1; i <= n; i++) { long long x; cin >> x; add(i, x); }
    while (m--) {
        int op; cin >> op;
        if (op == 1) { int i; long long v; cin >> i >> v; add(i, v); }
        else { int l, r; cin >> l >> r; cout << sum(r) - sum(l-1) << "\n"; }
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目