Вычислить сумму элементов в матрице эффективно

Ответ 1

Это то, что для таблиц суммированных зон. http://en.wikipedia.org/wiki/Summed_area_table

Шаг "preprocessing" состоит в том, чтобы построить новую матрицу того же размера, где каждая запись представляет собой сумму подматрицы в верхнем левом углу этой записи. Любая произвольная сумма подматрицы может быть рассчитана путем поиска и смешивания только 4 записей в SAT.

РЕДАКТИРОВАТЬ: Вот пример.

Для исходной матрицы

0 1 4
2 3 2
1 2 7

SAT

0 1 5
2 6 12
3 9 22

SAT получается с использованием S (x, y) = a (x, y) + S (x-1, y) + S (x, y-1) - S (x-1, y-1),

где S - матрица SAT, a - начальная матрица.

Если вы хотите получить сумму младшей правой 2х2 субматрицы, ответ будет равен 22 + 0 - 3 - 5 = 14. Это, очевидно, то же самое, что и 3 + 2 + 2 + 7. Независимо от размера матрицы, сумма подматрицы может быть найдена в 4 поиске и 3 арифметических операциях. Построение SAT - это O (n), аналогично требующее только 4 поисковых запросов и 3 математических аргумента на ячейку.

Ответ 2

Создайте новую матрицу, где entry (i,j) представляет собой сумму элементов в исходной матрице с более низкими или равными i и j. Затем, чтобы найти сумму элементов в подматрице, вы можете просто использовать постоянное количество базовых операций, используя углы подматрицы вашей суммарной матрицы.

В частности, найдите углы top_left, bottom_left, top_right и bottom_right вашей суммарной матрицы, где первые три находятся за пределами подматрицы, а bottom_right находится внутри. Тогда ваша сумма будет

bottom_right + top_left - bottom_left - bottom_right

Ответ 3

Вы можете сделать это с помощью динамического программирования. Создайте матрицу dp с размером n * m. И для каждого i, j, где

1 <= i <= n , 1 <= j <= m 
dp[i][j] will be : 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + values[i][j]

И для каждого запроса мы имеем lx, rx, ly, ry, где lx и rx - верхние левые координаты, ly и ry нижние правые координаты подматрицы.

1 ≤ lxi ≤ rx ≤ n, 1 ≤ ly ≤ ry ≤ m

sum = dp[rx][ry]  - dp[lx - 1][ry] - dp[rx][ly - 1] + dp[lx-1][ly - 1]

Посмотрите на картинку, чтобы понять, как работает алгоритм.

OD = dp[rx][ry], OB = dp[lx - 1][ry], OC = dp[rx][ly - 1], OA = dp[lx - 1][ly - 1]

Ответ 4

Это должно сработать. Вам всегда нужно пройти через каждый элемент в подматрице, чтобы выполнить добавление, и это самый простой способ.

* обратите внимание, что следующий код не может компилироваться, но он прав в псевдокоде

struct Coords{
    int x,y;
}

int SumSubMatrix(Coords topleft, Coords bottomright, int** matrix){
    int localsum = 0;
    for( int i = topleft.x; i <= bottomright.x; i++ ){
        for(int j = topleft.y; j <= bottomright.y; j++){
            localsum += matrix[i][j];
        }
    }
    return localsum;
}

Изменить: альтернативный метод предварительной обработки - создать другую матрицу из оригинала, содержащую суммы строк или столбцов. Вот пример: Оригинал:

0 1 4 
2 3 2
1 2 7

Матрица строк:

0 1 5
2 5 7
1 3 10

Матрица столбцов:

0 1 4
2 4 6
3 6 13

Теперь просто возьмите значения конечной точки x и вычтите значения начальной точки, например (для строк):

for( int i = topleft.y; i >= bottomright.y; i++ ){
    localsum += matrix2[bottomright.x][i] - matrix2[topleft.x][i];
}

Теперь это либо O (n), либо O (m)

Ответ 5

Ниже приведен пример реализации в C с использованием концепции суммированных табличных таблиц, как описано в одном из приведенных выше ответов.

Реализация Python для этого же может быть найдена по ссылке ниже - http://www.ardendertat.com/2011/09/20/programming-interview-questions-2-matrix-region-sum/

#include<stdio.h>

int pre[3][3];

int arr[3][3] = {
                {0,1,4},
                {2,3,2},
                {1,2,7}
                };

void preprocess()
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(i>0 && j>0)
            {
                 pre[i][j] = arr[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
            }
            else if(i>0 && j==0)
            {
                pre[i][j] = arr[i][j] + pre[i-1][j];
            }
            else if(j>0 && i==0)
            {
                pre[i][j] = arr[i][j] + pre[i][j-1];
            }
            else
            {
                pre[i][j] = arr[i][j];
            }                    
        }
    }
}

int subsum(int x1, int y1, int x2, int y2)
{
    preprocess();

    int ans = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];
    return ans;
}

int main()
{            
    printf("%d\n",subsum(1,1,2,2));
    return 0;
}