有人能給我提供二維二叉索引樹的算法嗎？

Question

我在網上搜索，但找不到一個好的。 我從geeksforgeeks.org獲得了一些幫助，但無法理解在更新BIT數組時從aux [i] [j]中減去v1-v2-v2-v4 + v3的構造部分。請讓我知道爲什麼我們在這裏扣除。

void constructAux(int mat[][N], int aux[][N+1]) 
{ 
    // Initialise Auxiliary array to 0 
    for (int i=0; i<=N; i++) 
     for (int j=0; j<=N; j++) 
      aux[i][j] = 0; 

    // Construct the Auxiliary Matrix 
    for (int j=1; j<=N; j++) 
     for (int i=1; i<=N; i++) 
      aux[i][j] = mat[N-j][i-1]; 

    return; 
} 

// A function to construct a 2D BIT 
void construct2DBIT(int mat[][N], int BIT[][N+1]) 
{ 
    // Create an auxiliary matrix 
    int aux[N+1][N+1]; 
    constructAux(mat, aux); 

    // Initialise the BIT to 0 
    for (int i=1; i<=N; i++) 
     for (int j=1; j<=N; j++) 
      BIT[i][j] = 0; 

    for (int j=1; j<=N; j++) 
    { 
     for (int i=1; i<=N; i++) 
     { 
      // Creating a 2D-BIT using update function 
      // everytime we/ encounter a value in the 
      // input 2D-array 
      int v1 = getSum(BIT, i, j); 
      int v2 = getSum(BIT, i, j-1); 
      int v3 = getSum(BIT, i-1, j-1); 
      int v4 = getSum(BIT, i-1, j); 

      // Assigning a value to a particular element 
      // of 2D BIT 
      updateBIT(BIT, i, j, aux[i][j]-(v1-v2-v4+v3)); 
     } 
    } 
    return; 
} 

Answer 1

對topcoder有二維索引樹的很好的解釋。

要了解aux[i][j]-(v1-v2-v4+v3)需要注意的是：

1. getSum(BIT,i,j)座標I，J與左上原點，和右下返回矩形的所有元素的總和。
因此
2. getSum(BIT, i, j)-getSum(BIT, i, j-1)是在j行的所有元素的跨過柱總和我
3. 因此getSum(BIT, i-1, j)-getSum(BIT, i-1, j-1)是在j行跨越到列中的所有元件中的位置的總和I-1
因此
4. v1-v2-v4+v3是條目的值i ，j

更新代碼的工作原理是在某個位置添加一個值。在此代碼中，他們希望將值設置爲aux[i][j]中的某個特定選項，因此實現該方法的方法是添加目標值與當前值之間的差異。

（話雖如此，該代碼更新依次在每個值，所以你會發現，V1-V2-V4 + V3總是等於零，因爲每一個值開始清除）