Есть матрица NxN. Нужно сосчитать суммы всех матриц MxM (M меньше N) внутри это исходной матрицы. Причем порядок алгоритма О(N*N).
Пока придумал только так:
1) Считаем суммы по столбикам и строкам всех элементов исходной матрицы и запоминаем это в полученный результат в матрицу S. (порядок NxN)
2)Считаем сумму первой матрицы, которая находится в (0,0) (порядок M)
3) Считаем суммы других матриц через предыдущие суммы и сумма столбиков и столбцов (порядок MxM)

Вроде все правильно, но громоздко и не прозрачно. Может быть есть идеи более изящного алгоритма?

P.S. могу подробнее описать

Исправьте тему на "Подсчет сумм квадратов"

(0) Может поможет: "Рекурсивная функция".

Ищи дерево отрезков, и дерево фенвика.
Правда сложность чуть хуже чем ты хочешь.

(3) не, надо именно N^N - условие задания.

(2) думал, но каким образом?

(3) я все равно не понял твою идею

(6) в смысле не понял? Дерево фенвика именно для твоей задачи и придумано. Конкретно для твоего случая есть статья на хабре.

http://habrahabr.ru/post/112828/ к (7)

(4) самих матриц O(n^3), так что ты со сложностью что-то напутал.

(8) читаю
(9) Задание "слово в слово":
Дан квадратный массив N*N и число M. Для каждого квадрата M*M (M < N) в этом массиве вычислить сумму его элементов. Общее число действий порядка N*N

(10) N*N многовато... -M надо

http://e-maxx.ru/algo/fenwick_tree

(10) а теперь прочитай что у тебя в (0) написано.
Ты разницы не видишь?

(12) ты говоришь, что N^3, но я же привел алгоритм N^2. Просто задание простое должно быть, и хочется изящный алгоритм

(13) нет

(13) а в чем ошибка скажи пожалуйста?

(15) в (0) у тебя написано посчитать сумму элементов для всех квадратных матриц, а в (10) сумму элементов квадратных матриц при заданном М.

пардон

может кто поправить (0)?

Для (10) дерево фенвика не нужно.
Мне сейчас не написать решение, я у зубного :)

ну ок, я подожду - не горит. лечись

Вычислим суммы элементов матриц размера MxM верхнего ряда матрицы NxN. На это потребуется N*M операций. (чтоб посчитать сумму элементов матрицы образованной сдвигом на один элемент влево - нужно прибависть сумму одного ряда, и отнять сумму одного ряда от предыдущей матрицы)
Вычислим так-же суммы элементов матриц MxM левого ряда матрицы NxN.
А далее, так как сумма элементов матрицы с верхним левым углом в элементе S(а,b) равна
S(a-1,b)+S(a,b-1)-S(a-1,b-1)+N(a+M-1,b+M-1)+N(a-1,b-1)-N(a-1,b+M-1)-N(a+M-1,b-1), то по-очереди можем посчитать сумму элементов всех матриц размера MxM.
N(a,b) - значение элемента [a,b] в начальной матрице. S(a,b) - сумма элементов в матрице MxM с началом (левым верхним углом) в элементе [a,b]

Спасибо, я мыслил так, но что то в этом направлении не получилось. Мб еще скину потом там посложнее задачка

завтра

(23)
Попробуй прежде чем считать подвести нормальную матбазу.
Например в скольких матрицах присутсвует число с позиции (1,1) или число с позиции (b,b)
Это если я правильно задачу понял

(25)
Тогда за один обход исходя из количества матриц для данной позиции можно высчитать суммы всех матриц

А нафига перебирать матрицы - неясно

(26) Можно еще раз?
Ты предлагаешь обойти все элементы начального массива, и приссумировать каждый ко всем матрицам в которых он присутствует? Поздравляю! Ты решил за O(N^2*M^2) задачу которая легко решается за O(N^2)

(28)
Сумма = 0;
Для Сч = 1 По N Цикл
  Для Сч = 1 По N Цикл
      Сумма = Сумма + А[Сч,Сч] * В(Сч,Сч);
  КонецЦикла;
КонецЦикла;

Где В(Сч1, Сч2) - в скольких матрицах встречается элемент А[Сч1;Сч2]

Осталось только определить функцию В - это легко

(29)
Там два разных счетчика, сори

(30) тебе вообще-то не одну сумму надо посчитать.

В ноль нужно отдельно посичтать сумму многих матриц.

(31)
А, значит я неправильно задачу понял