2

最后，我真的很想学习和实现分段树 2D。它困扰着我。我知道分段树的一维情况，但不知何故我无法用二维来管理。问题是我有一个矩阵 1024x1024 （所以我使用数组 [2048][2048] 作为树），我想实现两个操作：

  1. 无效插入（int x，int y，int val）；- 将值 val 分配给矩阵的元素 [x][y]
  2. 整数查询（整数 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 中应用它..

4

1 回答 1

0

好吧，您的案例确实返回 0 的原因是只执行了这部分代码：

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

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

这部分不会更改 res 因为条件从未满足：

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

我可以建议您在此处、此处、此处、此处和此处查看有关二叉树和区间树的信息和实现。

于 2012-07-18T13:22:35.900 回答