段树2D，矩形之和

我真的很想学习和实现段树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 ..

来源

2012-07-18 xan

为什么使用二维数组而不是“真正”的树？ – SingerOfTheFall 2012-07-18 13:02:27

我建议你使用'nodes'来实现你的树，因为通常会实现一棵树，我会告诉你使用递归而不是迭代方法来遍历树。你的'insert'和'query'可以用比现在少得多的行来实现。 – cybertextron 2012-07-18 13:07:55

我使用的是二维数组，因为它对我来说更容易首先完成。当我完成这个实现时，我会使用指针来编写它，使其更加优雅。 – xan 2012-07-18 13:17:07

那么，为什么你的情况下不会返回0的原因是，代码只有这部分被执行：

int res=tree[vx1][vy1]; 
if(vx1!=vx2 || vy1!=vy2) 
    res+=tree[vx2][vy2];

这里，res是0，因为tree[vx1][vy1]和tree[vx2][vy2]在你的情况下都是零。

这部分不会改变资源，因为条件，从来没有遇到过：

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];

所以，RES值不会改变，仍然是0。

现在，对整个事情。您正在以一种非常奇怪的方式构建细分树，实际上，您根本没有构建任何树，并且很难理解您使用该代码所做的工作。通常情况下，你想实现一个二叉树（其中段树）与看起来像节点链表：

struct node 
{ 
    int data; 
    node *left;   
    node *right; 
};

我会建议你在看here，here，here，here和here二进制和间隔树上的信息和实现。

来源

2012-07-18 13:22:35 SingerOfTheFall

段树2D，矩形之和

回答

相关问题