может кто-нибудь предоставить мне алгоритм двумерного двоичного индексированного дерева?

Я искал в интернете, но не смог найти хороший.
Я получил некоторую помощь от geeksforgeeks.org, но не могу понять строительную часть, где мы вычитаем v1-v2-v2-v4 + v3 из aux [i] [j] при обновлении массива BIT. Просто дайте мне знать, почему мы здесь вычитаем.

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

0

Решение

Есть хорошее объяснение 2d бинарных проиндексированных деревьев на 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 всегда равно нулю, потому что каждое значение начинается очищенным)

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector