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

Question

В одном из интервью меня спросили, была ли мне дана матрица n * m, как рассчитать сумму значений в данной подматрице (определенной по верхним левым, нижним правым координатам).

Мне сказали, что я могу предварительно обработать матрицу.

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

У кого-нибудь есть хороший ответ?

Answer 1

Для этого предназначены таблицы суммированных площадей. http://en.wikipedia.org/wiki/Summed_area_table

Ваш шаг «предварительной обработки» состоит в создании новой матрицы того же размера, где каждая запись является суммой подматрицы в верхнем левом углу этой записи. Любая произвольная сумма подматрицы может быть вычислена путем поиска и смешивания только 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, а - начальная матрица.

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

Answer 2

Вы можете сделать это с помощью динамического программирования. Создайте матрицу 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]

Answer 3

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

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

bottom_right + top_left - bottom_left - bottom_right

Answer 4

Ниже приведен пример реализации в 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;
}

Answer 5

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

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

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)