动态求连续区间和

给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b] 的连续和。

输入格式

第一行包含两个整数 n 和 m,分别表示数的个数和操作次数。

第二行包含 n 个整数,表示完整数列。

接下来 m行,每行包含三个整数 k,a,b (k=0,表示求子数列[a,b]的和;k=1,表示第 𝑎 个数加 b)。

数列从 1 开始计数。

输出格式

输出若干行数字,表示 k=0 时,对应的子数列 [a,b] 的连续和。

数据范围

1≤n≤100000
1≤m≤100000
1≤a≤b≤n
数据保证在任何时候,数列中所有元素之和均在 int 范围内。

输入样例:

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例:

11
30
35

#include<iostream>
using namespace std;
const int N=100010;
struct node
{
    int l,r;
    int sum;
};
int a[N];
node tr[4*N];
void push_up(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[r]};
    else
    {
        tr[u]={l,r};
        int mid=(l+r)>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        push_up(u);
    }
}
int query(int u,int l,int r)
{
    int res=0;
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    return res;
}
void modify(int u,int v,int x)
{
    if(tr[u].l==tr[u].r) tr[u].sum+=x;
    else
    {
       int mid=(tr[u].l+tr[u].r)>>1;
       if(v<=mid) modify(u<<1,v,x);
       else modify(u<<1|1,v,x);
       push_up(u);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!a) 
        {
            int t=query(1,b,c);
            printf("%d\n",t);  
        }
        else modify(1,b,c);
    }
    return 0;
}