分块

int n,a[MAXN],belong[MAXN];    int S,C,st[MAXN],ed[MAXN],sum[MAXN];        void pretreat()    {        S=int(sqrt(n));        for(int i=1;i<=n;i+=S){            st[++C]=i;            ed[C]=min(i+S-1,n);        }        for(int i=1;i<=C;i++)            for(int j=st[i];j<=ed[i];j++)                belong[j]=i,sum[j]+=a[i];    }        int update(int x,int k){        a[x]+=k;        sum[belong[x]]+=k;    }        int query(int x,int y){        int l=belong[x],r=belong[y],ans=0;        if(l==r){            for(int i=x;i<=y;i++)                ans+=a[i];        }        else{            for(int i=x;i<=ed[l];i++)                ans+=a[i];            for(int i=l+1;i

线段树

namespace Segment_Tree{    int n;    data t[MAXN*4];        inline int lc(int p){        return p<<1;    }    inline int rc(int p){        return p<<1|1;    }        void push_up(int p){        t[p]=t[lc(p)]+t[rc(p)];    }        void update(int x,data k,int left=1,int right=n,int p=1){        if(left==right)            t[p]=k;        else{            int mid=(left+right)>>1;            if(x<=mid)update(x,k,left,mid,lc(p));            else update(x,k,mid+1,right,rc(p));            push_up(p);        }    }        data query(int x,int y,int left=1,int right=n,int p=1){        if(x<=left&&right<=y)            return t[p];        else{            data ans;            int mid=(left+right)>>1;            if(x<=mid)ans=ans+query(x,y,left,mid,lc(p));            if(y>mid)ans=ans+query(x,y,mid+1,right,rc(p));            return ans;        }    }        data tag[MAXN];    inline void f(int p,int left,int right,data d){        tag[p]=tag[p]+d;        t[p]=t[p]+d.x*(right-left+1);    }    inline void push_down(int p,int left,int right){        data& d=tag[p];        int mid=(left+right)>>1;        f(lc(p),left,mid,d);        f(rc(p),mid+1,right,d);        d=data(0);    }        void update(int x,int y,data k,int left=1,int right=n,int p=1){        if(x<=left&&right<=y){            f(p,left,right,k);            return;        }        else{            push_down(p);            int mid=(left+right)>>1;            if(x<=mid)update(x,y,k,left,mid,lc(p));            if(y>mid)update(x,y,k,mid+1,right,rc(p));            push_up(p);        }    }    }~(1<<31)//int 所能到达的最大数 -b=~b+1//x&(-x)//

bzoj 2274

#include
     
      #include
      
       const int MAXN(100010);int n,s[MAXN];struct ovo{    int pos,value;}o[MAXN];inline bool operator<(const ovo& a,const ovo& b){    return a.value
       
        =1&&o[i].value!=o[i-1].value)            tot++;        s[o[i].pos]=tot;    }}const int P(int(1e9+9));int t[MAXN];inline int lowbit(int x){    return x&(-x);}inline void insert(int x,int k){    for(;x<=n;x+=lowbit(x))        t[x]=(t[x]+k)%P;}inline int query(int x){    int ans=0;    for(;x;x-=lowbit(x))        ans=(ans+t[x])%P;    return ans;}void work(){        f[0]=1;    for(int i=1;i<=n;i++)        for(int j=0;j
        
         =s[j])                f[i]+=f[j];    printf("%d\n",f[n]);        insert(s[0],1);    for(int i=1;i
        
       
      
     

 二维树状数组

#include
     
      int n,m;int t[1100][1100];inline int lowbit(int x){    return x&(-x);}inline void insert(int x,int y,int k){    for(int i=x;i<=n;i+=lowbit(i))        for(int j=y;j<=n;j+=lowbit(j))            t[i][j]+=k;}inline int query(int x,int y){    int ans=0;    for(int i=x;i;i-=lowbit(i))        for(int j=y;j;j-=lowbit(j))            ans+=t[i][j];    return ans;}int main(){    scanf("%d",&n);    while(true){        scanf("%d",&m);        if(m==1){            int x,y,k;            scanf("%d%d%d",&x,&y,&k);            x++,y++;            insert(x,y,k);        } else if(m==2) {            int x1,y1,x2,y2;            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);            x1++,y1++,x2++,y2++;            printf("%d\n",query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1));        } else{            break;        }    }    return 0;}