CPP进阶-线段树

C++进阶

线段树

例题ACWING242

const int N=1e5+5;
ll a[N],m,n;
struct tree{ll l,r,sum;}t[4*N];

建树(预处理)

void build(ll k,ll l,ll r){
    t[k].l=l,t[k].r=r;
    if(l==r)return;
    ll mid=l+r>>1;
    build(k<<1,l,mid);build((k<<1)+1,mid+1,r);
}

询问

ll quest(ll l,ll r,ll k){
    ll res=0;
    if(t[k].l>=l&&t[k].r<=r)return t[k].sum;
    ll mid=(t[k].l+t[k].r)/2;
    if(l<=mid)res=quest(l,r,k<<1);
    if(r>mid)res+=quest(l,r,k<<1|1);
    return res;
}

修改

void change(ll nk,ll k,ll d){
    t[nk].sum+=d;
    if(t[nk].l==t[nk].r)return;
    ll mid=(t[nk].l+t[nk].r)/2;
    if(k<=mid)change(nk<<1,k,d);
    else change((nk<<1)+1,k,d);
}

int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--){
        char op[2];
        ll x,l,r,d;
        scanf("%s",op);
        if(op[0]=='Q'){cin>>x;cout<>l>>r>>d;change(1,l,d);if(r