段樹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，矩形之和

回答

相關問題