洛谷 P3374——树状数组 / 树状数组模板题

洛谷 P3374——树状数组

#include <iostream>

using namespace std;

const int N = 5e5 + 10;

int tr[N], a[N];
int n, m;

int lowbit(int x)
{
    return x & -x;
}

void add(int u, int c)
{
    // 给所有管辖中有 a[i] 的 tr[] 加上 c
    for (int i = u; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int u)
{
    // 看 u 是哪几个 tr[i] 加起来的和
    // sum(u) 的值即为这些 tr[i] 的和
    int ans = 0;
    for (int i = u; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        add(i, a[i]); // 建树
    }
      
    while (m -- )
    {
        int type, x, y;
        cin >> type >> x >> y;
        
        if (type == 1) add(x, y);
        else cout << sum(y) - sum(x - 1) << '\n';
    }
    
    
    return 0;
}