题目大意
对一个数组实现单点修改与查询前缀和两个操作
解题思路
$add$函数对$c[x]$及其祖先节点进行更新
$query$函数把小区间的和都加起来
具体代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL c[N];
int a[N];
void add(int x, int t)
{
for (; x <= n; x += x & (-x))
c[x] += t;
}
LL query(int x)
{
LL res = 0;
for (; x; x -= x & (-x))
res += c[x];
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
add(i, a[i]);
}
while (m--)
{
int k, x, y;
cin >> k >> x >> y;
if (k)
{
add(x, y);
a[x] += y;
}
else
cout << query(y) - query(x - 1) << '\n';
}
return 0;
}