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 回答