Fenwick Tree——树状数组

问题陈述：
你得到一个长度为 N 的数组为 a0,a1,a2……an-1。处理以下类型的查询，一共有 Q 次查询。

0 p x : ap⬅ap + x
1 l r : 打印  ai  ( i=l 到 i=r-1 的 ai 之和)

约束：
1 ≤ N,Q ≤ 500000
0 ≤ ai,x ≤ 1e9
0 ≤ p < N
0 ≤ li < ri ≤ N
输入中的所有值都是整数

输入
输入由标准输入以以下格式给出：
N Q
a0 a1 ……an-1
Query0
Query1
.
.
QueryQ-1

输出
对于后一种类型的每个查询，打印答案。

Input
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Output
15
7
25
6

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int a[N],tr1[N],tr2[N];
int n,m;
int lowbit(int x)
{
    return x&-x;
}
void add(int tr[],int x,int c)
{
    for (int i=x;i<=n;i +=lowbit(i)) tr[i] +=c;
}
int sum(int tr[],int x)
{
    int ans=0;
    for (int i=x;i>0;i -=lowbit(i)) ans +=tr[i];
    return ans;
}
int is_sum(int x)
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}
signed main()
{
    ios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        add(tr1,i,b),add(tr2,i,i*b);
    }
    int s;
    while (m--)
    {
        cin>>s;
        if (s==0)
        {
            int l,c;
            cin>>l>>c;
            l++;
            add(tr1,l,c),add(tr1,l+1,-c);
            add(tr2,l,l*c),add(tr2,l+1,(l+1)*-c);
        }
        else 
        {
            int l,r;
            cin>>l>>r;
            l++,r++;
            cout<<is_sum(r-1)-is_sum(l-1)<<endl;
        }
    }
    return 0;
}