0

我在互联网上搜索，但找不到一个好的。我从 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;
}
4

1 回答 1

0

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 行到第 i 列的所有元素的总和
  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 总是等于零，因为每个值都开始清除）

于 2017-07-26T18:48:29.340 回答