вычислить сумму значения в прямоугольной области массива

Question

У меня есть очень большой массив большого значения и сохраните его в row-major 1d array.

ex: 
    1 2 3 
    4 5 6 

будет магазин в int* array = {1,2,3,4,5,6};

, что я должен сделать, учитывая row1, row2, column1, column2, а затем распечатать сумму района, и она запросит caulate другую область много раз.

то, что я думаю о нем сначала использовать вложенный цикл для обхода массива и хранить сумму каждой строки в sum_row и хранить сумму каждого столбца в sum_column и хранить суммы И. totalSum суммарной элементы.

Then totalSum - the row and the columns that surrond it + the elemnts that has been minus twice.

Но это кажется достаточно быстрым, есть ли какой-либо алгоритм, который может сделать быстрее или некоторые подсказки стиля кодирования, которые могут сделать фактор мало?

Thx заранее.

Answer 1

Мне кажется, что вы заменили одну двойную итерацию на другую. Проблема заключается в вычитании «the elemnts that has been minus twice»; если я не ошибаюсь, это требует повторения этих элементов, чтобы их суммировать.

Вместо этого просто перейдите по прямоугольной области, которую нужно суммировать. Я сомневаюсь, что это будет медленнее.

Более эффективный алгоритм может быть получен путем создания матрицы суммированных верхних левых матриц. (См. Статью в Википедии по адресу summed area table.) Затем вы можете вычислить любую сумму подматрицы, просмотрев четыре суммы площади.