最后,我真的很想学习和实现分段树 2D。它困扰着我。我知道分段树的一维情况,但不知何故我无法用二维来管理。问题是我有一个矩阵 1024x1024 (所以我使用数组 [2048][2048] 作为树),我想实现两个操作:
- 无效插入(int x,int y,int val);- 将值 val 分配给矩阵的元素 [x][y]
- 整数查询(整数 x1,整数 y1,整数 x2,整数 y2);- 返回矩形矩阵中元素的总和 (x1,y1,x2,y2)
到目前为止,我写了这个:
const int M=1024;
int tree[2*M][2*M];
void insert(int x, int y, int val) {
int vx=M+x, vy=M+y;
tree[vx][vy]=val;
while(vy!=1) {
vy/=2;
tree[vx][vy]=tree[vx][2*vy]+tree[vx][2*vy+1];
}
while(vx!=1) {
vy=M+y;
vx/=2;
while(vy!=1) {
vy/=2;
tree[vx][vy]=tree[2*vx][2*vy]+tree[2*vx+1][2*vy+1];
}
}
}
int query(int x1, int y1, int x2, int y2) {
int vx1=M+x1, vy1=M+y1, vx2=M+x2, vy2=M+y2;
int res=tree[vx1][vy1];
if(vx1!=vx2 || vy1!=vy2) res+=tree[vx2][vy2];
while(vx1/2 != vx2/2) {
vy1=M+y1; vy2=M+y2;
while(vy1/2 != vy2/2) {
if(vx1%2==0 && vy1%2==0) res+=tree[vx1+1][vy1+1];
if(vx2%2==1 && vy2%2==1) res+=tree[vx2-1][vy2-1];
vy1/=2; vy2/=2;
}
vx1/=2; vx2/=2;
}
return res;
}
但它不能正常工作。说,对于:
插入(5,5,1);查询(0,5,1000,5);
它返回0,而不是1。我认为问题出在查询中(我希望插入没问题),我不完全理解这个操作的想法。在 1D 中我没有任何问题,但对我来说,这种情况很难想象。
您能帮我正确实施吗?我将非常感谢您的帮助。
编辑:也许最好展示我如何在一维中做到这一点,这段代码有效,我认为这个想法很简单:
const int M=1024;
int tree[2*M];
void insert(int x, int val) {
int v=M+x;
tree[v]=val;
while(v!=1) {
v/=2;
tree[v]=tree[2*v]+tree[2*v+1];
}
}
int query(int a, int b) {
int va=M+a, vb=M+b;
int res=tree[va];
if(va!=vb) res+=tree[vb];
while(va/2 != vb/2) {
if(va%2==0) res+=tree[va+1];
if(vb%2==1) res+=tree[vb-1];
va/=2; vb/=2;
}
return res;
}
但不幸的是我不能在 2D 中应用它..