無聊中，寫了個二維線段樹。
N*N的矩陣里，兩種種操作
A x y w，a[x][y]加上w
S x1 y1 x2 y2，(x1,y1)到(x2,y2)這個小矩陣里所有數的和
二維線段樹:一維對x二分，每個節點也是一個線段樹，對y二分。
struct node{
int l,r,m;
int sum;
int num;
int pos;//treeX里每個節點的線段樹在treeY里的位置
}treeX[maxn*2],treeY[maxn*2][maxn*2];
int N;
int a[maxn][maxn];
int s[maxn][maxn];//s[i][j]表示（1，1）到(i,j)子矩陣的和
void buildY(int cnt,int ll,int rr,int root,int l,int r)
{
treeY[cnt][root].l = l;
treeY[cnt][root].r = r;
treeY[cnt][root].sum = s[rr][r]-s[rr][l-1]-s[ll-1][r]+s[ll-1][l-1];
if (l<r)
{
buildY(cnt,ll,rr,2*root,l,(l+r)/2);
buildY(cnt,ll,rr,2*root+1,(l+r)/2+1,r);
}
return ;
}
void buildX(int cnt,int root,int l,int r)
{
buildY(cnt,l,r,1,1,N);
treeX[root].l = l;
treeX[root].r = r;
treeX[root].sum = s[r][N]-s[l-1][N];
treeX[root].pos = cnt;
if (l<r)
{
buildX(cnt+1,2*root,l,(l+r)/2);
buildX(cnt+2,2*root+1,(l+r)/2+1,r);
}
return ;
}
int searchY(int cnt,int root,int l,int r)
{
if (l<=treeY[cnt][root].l && r>=treeY[cnt][root].r)
return treeY[cnt][root].sum;
int sum_l = 0, sum_r = 0;
int mid = (treeY[cnt][root].r + treeY[cnt][root].l)/2;
if (l<=mid)
sum_l = searchY(cnt,2*root,l,r);
if (r>mid)
sum_r = searchY(cnt,2*root+1,l,r);
return sum_l + sum_r;
}
int searchX(int root,int ll,int rr,int l,int r)
{
if (ll<=treeX[root].l && rr>=treeX[root].r)
return searchY(treeX[root].pos,1,l,r);
int sum_l = 0,sum_r = 0;
int mid = (treeX[root].l+treeX[root].r)/2;
if (ll<=mid)
sum_l = searchX(2*root,ll,rr,l,r);
if (rr>mid)
sum_r = searchX(2*root+1,ll,rr,l,r);
return sum_l + sum_r;
}
void addY(int cnt,int root,int y,int w)
{
treeY[cnt][root].sum += w;
if (treeY[cnt][root].l ==treeY[cnt][root].r)
return ;
int mid = (treeY[cnt][root].l + treeY[cnt][root].r)/2;
// puts("y");
if (y<=mid)
addY(cnt,2*root,y,w);
else
addY(cnt,2*root+1,y,w);
return ;
}
void addX(int root,int x,int y,int w)
{
treeX[root].sum += w;
addY(treeX[root].pos,1,y,w);
if (treeX[root].l == treeX[root].r)
return ;
// puts("x");
int mid = (treeX[root].l+treeX[root].r)/2;
if (x<=mid)
addX(2*root,x,y,w);
else
addX(2*root+1,x,y,w);
}
C和C++弱啊，該寫個模版的。