我真的很想学习和实现段树2D,最后。它困扰着我。我知道细分树的一维情况,但不知怎的,我无法用2D进行管理。的问题是,我有一个矩阵1024×1024(所以我使用的阵列[2048] [2048]作为树)和我想要实现两个操作:段树2D,矩形之和
- 空隙插入件(INT的x,INT Y,INT VAL ); - 其值VAL分配给元素[X]的矩阵[Y]
- INT查询(INT X1,Y1 INT,INT X2,Y2 INT); - 它返回长方形矩阵中的元素的总和(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我没有问题,但这种情况很难想象,对我来说。
你能帮我正确实施这个吗?我会非常感激的帮助。
编辑:也许这将是更好地展示我如何在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 ..
为什么使用二维数组而不是“真正”的树? – SingerOfTheFall 2012-07-18 13:02:27
我建议你使用'nodes'来实现你的树,因为通常会实现一棵树,我会告诉你使用递归而不是迭代方法来遍历树。你的'insert'和'query'可以用比现在少得多的行来实现。 – cybertextron 2012-07-18 13:07:55
我使用的是二维数组,因为它对我来说更容易首先完成。当我完成这个实现时,我会使用指针来编写它,使其更加优雅。 – xan 2012-07-18 13:17:07