2

ついにセグメントツリー2Dを学び、実装したいと思います。それは私を悩ませています。セグメント ツリーの 1D の場合は知っていますが、2D ではどうにもできません。問題は、1024x1024 の行列があり (したがって、配列 [2048][2048] をツリーとして使用する)、次の 2 つの操作を実装する必要があることです。

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

1 ではなく 0 が返されます。問題はクエリにあると思います (挿入が正常であることを願っています)。この操作の概念を完全には理解していません。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 には適用できません。

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 に答える