洛谷 P3374 【模板】树状数组 1

题目链接：https://www.luogu.com.cn/problem/P3374

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 500010;

int n, m, c[N];

// 返回x的二进制最右边1所对应的值
int lowbit(int x)
{
    return x & -x;
}

// 返回a[1]+...+a[x]的和
int ask(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
    {
        res += c[i];
    }
    return res;
}

// 令a[x] += y
void add(int x, int y)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        c[i] += y;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(i, x);
    }
    
    while (m--)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1)
        {
            add(x, y);
        }
        else
        {
            printf("%d\n", ask(y) - ask(x - 1));
        }
    }
    
    return 0;
}