Среднее подмножества в массиве, которое выходит за границы с постоянной сложностью

Question

Это вопрос к моей предыдущей проблеме, касающийся техник обработки 2d-массивов со сложностью o (1).

То есть получить среднее подмножества массива, но если это подмножество выходит за границы массива, принимая их за ноль. Это с двумерным массивом.

В действительности массив может go до [2000] [2000], но для простоты возьмем двумерный массив размером [4] [4].

array[4][4] = {0,  1,  2,  3
               4,  5,  6,  7
               8,  9,  10, 11
               12, 13, 14, 15}

Теперь предположим, что я хочу получить сумму массива между [2] [2] и [3] [3], то есть сложить 10 + 11 + 14 + 15 и разделить на четыре. Это может быть сделано в решении ao (1) с использованием методов «таблицы суммированных площадей» или «интегрального изображения».

Однако меня немного смущает вопрос о том, как сохранить сложность o (1), обеспечивающую / когда:

1. подмножество массива выходит за пределы фактического массива
2. индексы массива вне фактического массива принимаются равными нулю.
3. Алгоритм вычисления по-прежнему равен o (1)

Так, например, скажем, для этой суммы в пикселях меня просят получить сумму от [2] [2] до [4] [4]. Это имеет теоретический массив, числа вне фактического обозначаются f (для подделки) , но принимаются как ноль :

array_theory[5][5] = {0,  1,  2,  3,  0f
                      4,  5,  6,  7,  0f
                      8,  9,  10, 11, 0f
                      12, 13, 14, 15, 0f
                      0f, 0f, 0f, 0f, 0f}

или в изображении:

Итак, среднее значение между [2] [2] и [4] [4] составляет (10 + 11 + 0f + 14 + 15 + 0f + 0f + 0f + 0f) / 9

Я думаю, что должен использовать какой-то метод фильтрации или обработки изображений, который не может показаться ключевым словом, чтобы позволить мне найти / реализовать его, и я заигрываю с ним в результатах поиска.

Любая помощь будет принята с благодарностью!

Answer 1

Решение, которое вам было дано ранее для вычисления суммы элементов в подмассиве с одним углом в array[i0][j0] и другим углом в array[i1][j1] через O (1) времени после предварительной подготовки, заключается в подготовке массив sums, в котором sums[i][j] - это сумма всех элементов в подмассиве array[0][0] до array[i][j], после чего сумма произвольного подмассива может быть вычислена как sums[i1][j1] - sums[i1][j0-1] - sums[i0-1][j1] + sums[i0-1][j0-1], за исключением того, что любой из этих членов заменяется с 0, если любой из его индексов меньше нуля.

Чтобы расширить это за пределы больших краев массива, просто ограничьте слагаемые до их максимальных значений: если какой-либо нижний индекс превышает последний действительный индекс массива, замените его последним допустимым индексом массива.

Мы могли бы определить вспомогательную функцию для доступа sums:

/*  Return sums[i][j] from an array that is physically r rows and c columns
    but is conceptually extended infinitely on all four sides as if
    arrays[i][j] contained zeros for all elements outside the physical
    array.
*/
Type Sums(ssize_t r, ssize_t c, Type sums[r][c], ssize_t i, ssize_t j)
{
    if (i < 0 || j < 0) return 0;
    if (r <= i) i = r-1;
    if (c <= j) j = c-1;
    return sums[i][j];
}

Тогда сумма элементов в подмассив от array[i0][j0] до array[i1][j1] - это просто Sums[i1][j1] - Sums[i1][j0-1] - Sums[i0-1][j1] + Sums[i0-1][j0-1], а среднее, конечно, (Sums[i1][j1] - Sums[i1][j0-1] - Sums[i0-1][j1] + Sums[i0-1][j0-1]) / ((j1-j0+1) * (i1-i0+1)).