【福利】二维线段树的代码

这个线段树是以二叉树结点的形式写的，一维线段树不知道如何扩展的可以戳这里看看二维的是如何划分平面的。

头文件自己脑补

struct Node{
int x1,y1,x2,y2,c1,c2,c3,c4,cover,sum;
} tree[600000];
int tot=0;
int xl,yl,xr,yr,num,ans=0;
//xl,yl,xr,yr参考一维情况的c和d是怎么用的
void build(int x1,int y1,int x2,int y2){
int now=++tot;
tree[now].x1=x1;
tree[now].y1=y1;
tree[now].x2=x2;
tree[now].y2=y2;
tree[now].c1=0;//c1还好，下面的必须赋值保证是0，否则你就死循环吧（1*2的空间没有右上和右下象限，1*1的空间只有左上c1空间可以用）如果不懂可以见下面的图
tree[now].c2=0;
tree[now].c3=0;
tree[now].c4=0;
tree[now].cover=0;
tree[now].sum=0;
int midx=(x1+x2)>>1;
int midy=(y1+y2)>>1;
if(midx<x2||midy<y2){
tree[now].c1=tot+1;
build(x1,y1,midx,midy);
}
if(midx<x2){
tree[now].c2=tot+1;
build(midx+1,y1,x2,midy);
}
if(midy<y2){
tree[now].c3=tot+1;
build(x1,midy+1,midx,y2);
}
if(midx<x2&&midy<y2){
tree[now].c4=tot+1;
build(midx+1,midy+1,x2,y2);
}
}
//对xl，yl，xr，yr，num（区间增加的值）赋值后调用change（1）；
void change(int Num){
if(xl<=tree[Num].x1&&yl<=tree[Num].y1&&xr>=tree[Num].x2&&yr>=tree[Num].y2){
tree[Num].cover+=num;
}
else{
int midx=(tree[Num].x1+tree[Num].x2)>>1;
int midy=(tree[Num].y1+tree[Num].y2)>>1;
int dy=min(tree[Num].y2,yr);
int kx=max(tree[Num].x1,xl);
int dx=min(xr,tree[Num].x2);
int ky=max(tree[Num].y1,yl);
tree[Num].sum+=num*max(0,dx-kx+1)*max(0,dy-ky+1);
if(tree[Num].c1&&xl<=midx&&yl<=midy)change(tree[Num].c1);
if(tree[Num].c2&&xr>=midx+1&&yl<=midy)change(tree[Num].c2);
if(tree[Num].c3&&xl<=midx&&yr>=midy+1)change(tree[Num].c3);
if(tree[Num].c4&&xr>=midx+1&&yr>=midy+1)change(tree[Num].c4);
}
}
//对xl，yl，xr，yr，ans=0赋值后调用find（1）；
void find(int Num){
if(xl<=tree[Num].x1&&yl<=tree[Num].y1&&xr>=tree[Num].x2&&yr>=tree[Num].y2){
ans+=tree[Num].cover*(tree[Num].x2-tree[Num].x1+1)*(tree[Num].y2-tree[Num].y1+1)+tree[Num].sum;
}
else{
int midx=(tree[Num].x1+tree[Num].x2)>>1;
int midy=(tree[Num].y1+tree[Num].y2)>>1;
int dy=min(tree[Num].y2,yr);
int kx=max(tree[Num].x1,xl);
int dx=min(xr,tree[Num].x2);
int ky=max(tree[Num].y1,yl);
ans+=tree[Num].cover*max(0,dx-kx+1)*max(0,dy-ky+1);
if(tree[Num].c1&&xl<=midx&&yl<=midy)find(tree[Num].c1);
if(tree[Num].c2&&xr>=midx+1&&yl<=midy)find(tree[Num].c2);
if(tree[Num].c3&&xl<=midx&&yr>=midy+1)find(tree[Num].c3);
if(tree[Num].c4&&xr>=midx+1&&yr>=midy+1)find(tree[Num].c4);
}
}
int main(){
int i,j,k,m,n,t;
tot=0;
build(1,1,100,100);
xl=2,yl=2,xr=100,yr=100,num=1;
change(1);
//测试用
xl=2,yl=2,xr=100,yr=100,ans=0;
find(1);
//测试用
cout<<ans<<endl;
cout<<"I*m successful!\n";
system("pause");
}
百度百科里我也扩充了这个。