C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int w[N];
struct node
{
    int l;//l,r代表该节点所覆盖的范围 
    int r;// 
    int sum;//覆盖范围内所有值的和 
}tr[N*4];
// u<<1 左儿子 
// u<<1|1 右儿子 
void pushup(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)//到达了叶节点
    {
        node no;no.l=l;no.r=r;no.sum=w[r];
        tr[u]=no;
    }   
    else
    {
        node no;no.l=l;no.r=r;
        tr[u]=no;//先确定范围 
        int mid = l + r >> 1;//确定左儿子与右儿子的分割线 
        build(u<<1,l,mid);//递归左儿子 
        build(u<<1|1,mid+1,r);//递归右儿子 
        pushup(u);//计算父亲的值 
    } 
}

int query(int u,int l,int r)//节点编号与范围 
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;//完全包含,该节点在所求范围之内 
    int mid = tr[u].l + tr[u].r >> 1;//左右儿子的分割点 
    int sum=0;
    if(l<=mid)sum=query(u<<1,l,r);//如果左儿子在范围内 
    if(r>mid)sum+=query(u<<1|1,l,r);//右儿子在范围内 
    return sum;
}

void modify(int u,int x,int v)//根节点，位置，值 
{
    if(tr[u].l==tr[u].r)tr[u].sum+=v;//到达根节点，加上值
    else
    {
        int mid=tr[u].l+tr[u].r >>1;
        if(x<=mid)modify(u<<1,x,v);//目标值在左儿子范围内 
        else modify(u<<1|1,x,v);//目标在右儿子范围内 
        pushup(u);//儿子加上值后，动态重新计算父亲的值 
     } 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    build(1,1,n);
    int k,a,b;
    while(m--)
    {
        cin>>k>>a>>b;
        if(k==0)cout<<query(1,a,b)<<endl;
        else modify(1,a,b);
    }
}