1. Идея

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

Если для каждого запроса просто перебрать все клетки внутри прямоугольника, то это будет слишком долго: запросов до 2 * 10^5, а сама таблица может быть размером до 1000 x 1000.

Поэтому надо один раз сделать предварительные вычисления, чтобы потом отвечать на каждый запрос за O(1).

Для этого используются двумерные префиксные суммы.

2. Наблюдения

Пусть pref[i][j] — сумма всех элементов в прямоугольнике от (1, 1) до (i, j) включительно.

Тогда:

• pref[i - 1][j] — сумма всего, что выше текущей строки;
• pref[i][j - 1] — сумма всего, что левее текущего столбца;
• если их просто сложить, общая часть посчитается дважды, поэтому нужно вычесть pref[i - 1][j - 1];
• затем добавить значение текущей клетки.

Получаем формулу: pref[i][j] = a[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]

Теперь разберём запрос (r1, c1, r2, c2).

Сумма в прямоугольнике от (r1, c1) до (r2, c2) получается из большого префикса pref[r2][c2]:

1. убираем всё, что выше строки r1: pref[r1 - 1][c2]
2. убираем всё, что левее столбца c1: pref[r2][c1 - 1]
3. область в левом верхнем углу вычлась дважды, значит её надо вернуть: pref[r1 - 1][c1 - 1]

Итоговая формула: ans = pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1]

3. Алгоритм

1. Считываем r и c.
2. Создаём таблицу pref размера (r + 1) x (c + 1), заполненную нулями.
   • Дополнительная нулевая строка и нулевой столбец нужны, чтобы удобно обрабатывать границы.
3. Читаем исходную таблицу построчно и сразу строим pref.
4. Считываем количество запросов q.
5. Для каждого запроса:
   • читаем r1, c1, r2, c2;
   • считаем ответ по формуле через префиксные суммы;
   • выводим ответ.

4. Почему это работает

Докажем корректность по частям.

Построение префиксной суммы

pref[i][j] должен хранить сумму всех клеток прямоугольника с углами (1, 1) и (i, j).

При вычислении:

• pref[i - 1][j] содержит сумму всех строк от 1 до i - 1 в столбцах от 1 до j;
• pref[i][j - 1] содержит сумму всех строк от 1 до i в столбцах от 1 до j - 1;
• их пересечение, то есть прямоугольник (1, 1) ... (i - 1, j - 1), посчитано два раза, поэтому вычитаем pref[i - 1][j - 1];
• после этого добавляем значение клетки (i, j).

Значит, формула действительно даёт сумму нужного прямоугольника.

Ответ на запрос

Рассмотрим прямоугольник от (r1, c1) до (r2, c2).

• pref[r2][c2] — сумма всех клеток от (1, 1) до (r2, c2);
• pref[r1 - 1][c2] убирает лишнюю верхнюю часть;
• pref[r2][c1 - 1] убирает лишнюю левую часть;
• но верхний левый прямоугольник вычтен дважды, поэтому добавляем pref[r1 - 1][c1 - 1].

После этого остаются ровно клетки нужного подпрямоугольника.

Следовательно, каждый ответ вычисляется правильно.

5. Сложность

Построение таблицы префиксных сумм занимает O(r * c).

Каждый запрос обрабатывается за O(1).

Итоговая сложность: O(r * c + q)

По памяти хранится таблица pref размера (r + 1) x (c + 1), то есть: O(r * c)

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int r, c;
    cin >> r >> c;

    vector<vector<long long>> pref(r + 1, vector<long long>(c + 1, 0));

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            long long x;
            cin >> x;
            pref[i][j] = x + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long ans = pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1];
        cout << ans << '\n';
    }

    return 0;
}

7. Код на Python 3

r, c = map(int, input().split())

pref = [[0] * (c + 1) for _ in range(r + 1)]

for i in range(1, r + 1):
    row = list(map(int, input().split()))
    for j in range(1, c + 1):
        x = row[j - 1]
        pref[i][j] = x + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]

q = int(input())
for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    ans = pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1]
    print(ans)