思路与算法

初始数列全0，用树状数组维护点加和前缀和。操作0把指定位置增加b；操作1查询 [a,b]，用 prefix(b)-prefix(a-1) 得到区间和。按输入顺序处理全部操作。

正确性说明

树状数组中的每个节点维护一个由lowbit决定的区间和。点加会更新所有包含该位置的节点，前缀查询使用互不重叠的这些区间覆盖1到x。因此两个前缀之差恰好留下[a,b]，就是当前区间的连续和。

复杂度

初始化 O(N)，总时间 O(N+M log N)，空间 O(N)。

易错点

没有初始数组这一行；操作0是点加，操作1是查询。与其他题目的操作编号可能相反。增量和累计区间和不是同一范围，累计和可能超过32位，需使用long long。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> bit(n + 1);
    auto prefix = [&](int p) {
        long long sum = 0;
        for (; p; p -= p & -p)
            sum += bit[p];
        return sum;
    };
    while (m--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 0) {
            for (int p = a; p <= n; p += p & -p)
                bit[p] += b;
        } else
            cout << prefix(b) - prefix(a - 1) << '\n';
    }
}