c++ - 2D线段树，矩形之和

Question

我真的很想学习和实现 segment tree 2D，终于。它困扰着我。我知道线段树的 1D 情况，但不知何故我无法使用 2D 进行管理。问题是我有一个 1024x1024 矩阵(所以我使用数组 [2048][2048] 作为树)并且我想实现两个操作:

1. void insert(int x, int y, int val); - 将值 val 分配给矩阵的元素 [x][y]
2. int query(int x1, int y1, int x2, int 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 中我没有遇到任何问题，但这种情况对我来说很难想象。

你能帮我正确实现吗？如果您能提供帮助，我将不胜感激。

编辑:也许展示我如何在 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 中应用它..

Answer 1

嗯，你的case之所以返回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有关二叉树和区间树的信息和实现。