#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define maxn 500005
#define maxm 800005
using namespace std; int n,m,cnt,sum[maxn],pos[maxm],ans[maxm];
struct date{
int op,x,y,v,id;
}qs[maxm]; bool comp(date x,date y){
return x.x<y.x;
} int lowbit(int x){
return x&(-x);
} void add(int x,int y){
for (int i=x;i<=n;i+=lowbit(i)){
sum[i]+=y;
}
} int query(int x){
int temp=;
for (int i=x;i>;i-=lowbit(i)){
temp+=sum[i];
}
return temp;
} void cdq_solve(int l,int r){
if (l==r) return;
int mid=(l+r)/,temp=;
cdq_solve(l,mid),cdq_solve(mid+,r);
sort(qs+l,qs+mid+,comp),sort(qs+mid+,qs+r+,comp);
int i=l,j=mid+;
while (j<=r){
while (qs[i].op==&&i<=mid) i++;
while (qs[j].op==&&j<=r) j++;
if (i<=mid&&qs[i].x<=qs[j].x) add(qs[i].y,qs[i].v),i++,temp=i-;
else if (j<=r) ans[qs[j].id]+=query(qs[j].y),j++;
}
for (int t=l;t<=temp;t++) if (qs[t].op==) add(qs[t].y,-qs[t].v);
} int main(){
memset(ans,,sizeof(ans));
memset(sum,,sizeof(sum));
int op,x1,x2,y1,y2;
scanf("%d",&n),m=cnt=;
for (;;){
scanf("%d",&op);
if (op==){
qs[++m].op=op,qs[m].id=m;
scanf("%d%d%d",&qs[m].x,&qs[m].y,&qs[m].v);
}else{
if (op==){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
pos[++cnt]=m;
qs[++m].op=op,qs[m].x=x1-,qs[m].y=y1-,qs[m].id=m;
qs[++m].op=op,qs[m].x=x2,qs[m].y=y2,qs[m].id=m;
qs[++m].op=op,qs[m].x=x1-,qs[m].y=y2,qs[m].id=m;
qs[++m].op=op,qs[m].x=x2,qs[m].y=y1-,qs[m].id=m;
}else break;
}
}
cdq_solve(,m);
for (int i=;i<=cnt;i++) printf("%d\n",ans[pos[i]+]+ans[pos[i]+]-ans[pos[i]+]-ans[pos[i]+]);
}
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2683
题目大意：给定一个n*n的矩形，以及若干个操作，操作有如下两种：
1.给矩形的（x，y）加上一个v；
2.询问某个子矩阵的权值和。
数据范围：n<=5*10^5,操作数<=2*10^5;
初看这题，尼玛这不是二维树状数组（二维线段树也行，不过是作死）傻逼题吗，期望复杂度O（nlog^2 n），空间复杂度n^2，再一看数据范围，GG。
在ls神犇的教导下，我学会了四种通过此题的方法：1.二维线段树动态开点，空间复杂度nlog^2 n），有点卡空间。
2.二维树状数组+hash表，可惜我没掌握这种正确姿势-.-；
3.线段树套平衡树，线段树维护x坐标，每一层套一个splay，以y坐标为关键字，对于一个询问，拆成四个矩阵，再在对应的线段树中在splay中去找，更新答案即可，据说这种写法空间复杂度只有O（n）的复杂度，可以过。
4.进入正题吧，这题的最佳姿势是cdq分治+树状数组维护区间和；
前三种做法略过（在线做法），说说第四种做法（离线做法）吧：
我先来说说cdq_分治的流程吧，cdq分治一般是解决具有一下两种性质的问题（只有修改和查询操作）：
1.只能用离线做法。
2.每个修改操作对询问的影响是独立的，即与之前的修改操作无关。
cdq分治与一般的分治不同，一般的分治分出来的子区间是独立的，个个击破即可，而cdq分治分出来的两个子区间是相互联系的。（以下的分治都是指cdq分治）
由于在该问题中，每个询问只与在此之前的修改操作有关。
对于区间l，mid，记为区间1，区间mid+1，r，记为区间2，
过程：
1.递归处理区间(1)，
2.递归处理区间(2)，
3.统计区间1中的修改操作对区间2中的询问操作的影响。
4.算法结束。
关键在于第3步，对于这个题，我们将两个区间各自按x坐标排序，然后用两个指针分别去扫一遍，遇到区间1中的修改操作，就把纵坐标加入树状数组，然后及时统计区间2中询问的答案即可。具体细节可见代码。
cdq分治+树状数组