题目描述

支持单点修改，区间查询

样例

blablabla

就刚学了CDQ分治，正好做一道树状数组裸题练练手。
考虑树状数组的做法，先将序列变为差分序列，然后单点修改变为两个单点修改，查询是查前缀和。
那么CDQ也是一样的（我默认你们都懂CDQ那一套理论了），定义操作结构体：

struct Node{
    int type;//操作类型;
    int idx;//操作序列元素的位置;
    int val;//修改的值或者第几次查询;
    bool operator <(const Node& x)const{
        if(idx!=x.idx) return idx<x.idx;
        return type<x.type;
    }
};

那么序列初始值可以看做是修改操作，然后修改操作拆成两个单点修改，查询就是查前缀和。
然后像归并排序那个样子进行CDQ就好啦。

算法1

(CDQ分治) $O(n*log_2(n))$

blablabla

时间复杂度分析：就归并啊

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;


const int maxn=1e5+7;

const int maxm=4e5+7;

struct Node{
    int type;
    int idx;
    int val;
    bool operator <(const Node& x)const{
        if(idx!=x.idx) return idx<x.idx;
        return type<x.type;
    }
}query[maxm],temp[maxm];

ll ans[maxm];

void CDQ(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);

    int p=l,q=mid+1;
    ll sum=0;
    int o=0;
    while(p<=mid&&q<=r){
        if(query[p]<query[q]){
            if(query[p].type==1) sum+=query[p].val;
            temp[o++]=query[p++];
        }
        else{
            if(query[q].type==2) ans[query[q].val]+=sum;
            temp[o++]=query[q++];
        }
    }
    while(p<=mid) temp[o++]=query[p++];
    while(q<=r){
        if(query[q].type==2) ans[query[q].val]+=sum;
        temp[o++]=query[q++];
    }

    for(int i=0;i<o;++i) query[l+i]=temp[i];
}
char s[9];

int a[maxn];
int main(){
    int n,w;
    scanf("%d%d",&n,&w);
    int l,r,id,x;
    int idx=0,time=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        ++idx;
        query[idx].type=1,query[idx].idx=i,query[idx].val=a[i]-a[i-1];
    }
    for(int i=1;i<=w;++i){
        scanf("%s%d",s,&l);
        if(s[0]=='Q'){
            ++idx;
            ++time;
            query[idx].type=2,query[idx].idx=l,query[idx].val=time;
        }
        else{
            scanf("%d%d",&r,&x);
            ++idx;
            query[idx].type=1,query[idx].idx=l,query[idx].val=x;
            ++idx;
            query[idx].type=1,query[idx].idx=r+1,query[idx].val=-x;
        }
    }
    CDQ(1,idx);
    for(int i=1;i<=time;++i) printf("%lld\n",ans[i]);

    return 0;
}