1. Идея

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

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

Стандартная идея для таких задач — построить двумерные префиксные суммы. Тогда сумму на любом подпрямоугольнике можно находить за O(1) после предварительной обработки.

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

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

Тогда:

• pref[i - 1][j] — сумма выше текущей строки,
• pref[i][j - 1] — сумма левее текущего столбца,
• если их сложить, прямоугольник (1, 1) ... (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).

Если взять pref[r2][c2], то это сумма во всём прямоугольнике от (1, 1) до (r2, c2). Но там есть лишние части:

• строки выше r1: это pref[r1 - 1][c2],
• столбцы левее c1: это pref[r2][c1 - 1].

Однако прямоугольник в левом верхнем углу pref[r1 - 1][c1 - 1] мы вычли дважды, значит его надо вернуть.

Итог:

answer = 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. Для каждой клетки таблицы:
   • считать значение x,
   • вычислить pref[i][j] по формуле префиксной суммы.
4. Считать число запросов q.
5. Для каждого запроса:
   • считать r1, c1, r2, c2,
   • вычислить ответ по формуле включения-исключения,
   • вывести результат.

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

Докажем корректность в двух частях.

Построение pref

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

Рассмотрим формулу:

pref[i][j] = x + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]

Здесь:

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

Значит, после вычисления формула действительно даёт сумму по всему прямоугольнику (1, 1) ... (i, j).

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

Нужно найти сумму в прямоугольнике (r1, c1) ... (r2, c2).

Берём весь большой прямоугольник:

• pref[r2][c2]

Убираем лишнее:

• верхнюю часть: pref[r1 - 1][c2]
• левую часть: pref[r2][c1 - 1]

Но их пересечение, то есть левый верхний прямоугольник pref[r1 - 1][c1 - 1], было вычтено дважды. Поэтому его надо добавить обратно.

Именно поэтому ответ равен:

pref[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)
• память: O(r * c)

При данных ограничениях это подходит.

6. Код на C++17

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

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

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

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            int 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;

        int 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)