实际上一般就不会操作原始的 a[] 数组了，但这边还是保留有 a[] 数组的代码。

注意在进行过修改之后我没有同步修改 a[] 的值。

$O(n\log n)$ 建树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int t[MAXN + 5];
int lowbit(int x)
{
    return x & (-x);
}
// 第x个数加k
void update(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}
// 返回前x个数的和
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        update(i, a[i]);
    }
    while (m--)
    {
        int op, x, y;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y; // a[x]+=y
            update(x, y);
        }
        else
        {
            cin >> x >> y; // cout sum(a[x]~a[y])
            cout << query(y) - query(x - 1) << "\n";
        }
    }
    return 0;
}

$O(n)$ 建树

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        t[i] += a[i];
        if (i + lowbit(i) <= n)
            t[i + lowbit(i)] += t[i];
    }