题解 | #Big Water Problem#

思路

看数据范围1e5，暴力求和会被查询卡掉，用前缀和会被单点修改卡掉，所以我们要用到线段树。
线段树（查询+单点修改），背板代码如下。
我的码风把int定义成ll了，希望你们看的习惯。

代码

#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int maxn=100005;
int n,m,f,x,y,a[maxn],tree[maxn*4];

void build(int node,int start,int end){
    if(start==end){
        tree[node]=a[start];
        return;
    }
    int mid=start+end>>1;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

void add(int node,int start,int end,int num,int val){
    if(start==end){
        tree[node]=val;
        a[num]=val;
        return;
    }
    int mid=start+end>>1;
    if(num<=mid) add(node<<1,start,mid,num,val);
    if(num>mid) add(node<<1|1,mid+1,end,num,val);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

int query(int node,int start,int end,int l,int r){
    if(l<=start&&end<=r) return tree[node];
    int mid=start+end>>1;
    int res=0;
    if(l<=mid) res+=query(node<<1,start,mid,l,r);
    if(r>mid) res+=query(node<<1|1,mid+1,end,l,r);
    return res; 
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&f,&x,&y);
        if(f==1) add(1,1,n,x,a[x]+y);
        else if(f==2) cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}