洛谷P3374线段树 单点增减 区间求和

题目传送 洛谷P3374

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int sum[maxn*4],a[maxn];
int N,M,ans,b,c;
char s[10];//若输入的操作标志为字符，也应按照字符串去输入，否则char一个字符会读入回车和空格，可能爆内存。
int build(int l,int r,int root){  //递归建树
    if(l==r)return sum[root]=a[l];
    else{
        int mid=(l+r)/2;
        return sum[root]=build(l,mid,root*2)+build(mid+1,r,root*2+1);
    }
}
void updt(int l,int r,int root){//单点加减
    sum[root]+=c;
    if(l==r)return;
    else{
        int mid=(l+r)/2;
        if(b<=mid)updt(l,mid,root*2);
        if(b>=mid+1)updt(mid+1,r,root*2+1);
    }
}
int query(int l,int r,int root){//区间求和
    if(b<=l&&c>=r)return ans+=sum[root];
    else{
        int mid=(l+r)/2;
        if(b<=mid)query(l,mid,root*2);
        if(c>=mid+1)query(mid+1,r,root*2+1);
    }
    return ans;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        scanf("%d",&a[i]);
    build(1,N,1);
    for(int j=1;j<=M;j++){
        scanf("%s%d%d",s,&b,&c);
        if(s[0]=='1'){
            updt(1,N,1);
        }
        if(s[0]=='2'){
            ans=0;
            query(1,N,1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

左移运算符用“<<”表示，是将运算符左边的对象，向左移动运算符右边指定的位数，并且在低位补零。其实，向左移n 位，就相当于乘上2 的n 次方