Сумма на подотрезке

Пусть имеется массив $a$ длины $n$ и $q$ запросов вида $l, r$ и требуется для каждого запроса посчитать

\[S_{lr} = a_l + a_{l+1} + \dots + a_{r} \text{ - нумерация везде с нуля.}\]

Существует очевидное решение данной задачи со сложностью $O(nq)$: проход по массиву $a$ от $l$ до $r$ для каждого запроса с подсчётом суммы.

Оказывается, у данной задачи есть решение с заметно лучшей асимптотикой $O(n + q)$, однако оно потребует построения дополнительного массива $p$.

Скажем, что $p_i$ - сумма первых $i$ элементов массива $a$. Для простоты определим $p_0 = 0$.

Массив $p$ очень легко посчитать за асимптотику $O(n)$ циклом $for$:

\[i > 0 : p_i = p_{i-1} + a_{i-1}\]

Заметим, что

\[a_l + a_{l+1} + \dots + a_{r} = p_r - p_{l - 1}\]

Это легко понять, если подставить $p$ как суммы $a_i$.

Тогда после подсчёта массива $p$ мы можем отвечать на запрос за $O(1)$ времени, вычисляя разность нужных значений $p$.

Таким образом и получается итоговая сложность $O(n + q)$.

Сумма в подматрице

Аналогичную идею можно использовать для быстрого поиска суммы в подматрице.

Для этого понадобится дополнительный двумерный массив $p$. Однако теперь $p_{ij}$ - это сумма в подматрице c левым верхним углом в $(0, 0)$ и правым нижнем в $(i, j)$.

Воспользовавшись идеей формулы включений-исключений или нарисовав картинку, получим формулу пересчета для массива $p$:

\[p_{i,j} = p_{i-1, j} + p_{i, j-1} - p_{i-1, j-1}\]

Тогда сумма на подматрице c левым верхним углом в $(i_1, j_1)$ и правым нижнем в $(i_2, j_2)$.

\[S_{(i_1, j_1), (i_2, j_2)} = p_{i_2, j_2} - p_{i_1-1, j_2} - p_{i_2, j_1-1} + p_{i_1-1, j_1-1}\]