树状数组2

依旧用树状数组

#include<iostream>
using namespace std;
const int N=5e5+5;
typedef long long ll;//不开long long好像也行，我没试过
ll a[N],c[N],n,m;
int lowbit(ll x){
    return x & (-x);
}//计算x在二进制下的最小位的1的值
void update(ll x,ll v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}//单点修改
ll sum(ll x){
    ll ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}//计算区间和
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]-a[i-1]);
        //这道题用到差分思想，所以输入也要跟差分一样
    }
    while(m--){
        ll op;
        cin>>op;
        if(op==1){
            ll x,y,k;
            cin>>x>>y>>k;
            update(x,k);//先将0~x的数都加k
            update(y+1,-k);//再将0~y+1都减k，同样也是差分
        }else if(op==2){
            ll x;
            cin>>x;
            cout<<sum(x)<<"\n";
        }
    }
    return 0;
}