1. Идея

Нужно обработать m прибавлений на отрезках, а потом ответить на q запросов суммы на отрезке.

Если делать каждую операцию напрямую, прибавляя v ко всем элементам от l до r, то одна операция может занимать O(n), и это слишком медленно при n, m, q до 2 * 10^5.

Здесь используется стандартная связка из двух идей:

• разностный массив — чтобы быстро выполнить все прибавления на отрезках;
• префиксные суммы — чтобы быстро отвечать на запросы сумм.

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

Наблюдение 1. Как быстро делать прибавление на отрезке

Пусть есть массив a[1..n], изначально весь из нулей.

Чтобы прибавить v ко всем элементам на отрезке [l, r], можно не изменять все элементы по одному, а хранить разностный массив diff.

Для операции [l, r]:

• diff[l] += v
• diff[r + 1] -= v, если r + 1 <= n

После этого, если пройти слева направо и накапливать сумму значений diff, получится итоговый массив бонусов по дням.

Почему это работает:

• начиная с позиции l, значение увеличивается на v;
• после позиции r это увеличение отменяется.

Наблюдение 2. Как быстро отвечать на суммы отрезков

После того как итоговый массив бонусов по дням восстановлен, запрос суммы на отрезке [l, r] можно считать через ещё один префиксный массив.

Если pref[i] — сумма бонусов на днях от 1 до i, то ответ на запрос:

• pref[r] - pref[l - 1]

Это даёт ответ за O(1) на каждый запрос.

3. Алгоритм

Шаг 1. Считываем операции и строим разностный массив

Создаём массив diff размера n + 2, заполненный нулями.

Для каждой операции l, r, v:

• увеличиваем diff[l] на v
• если r + 1 <= n, уменьшаем diff[r + 1] на v

Шаг 2. Восстанавливаем итоговые бонусы и сразу строим префикс сумм

Будем идти по дням от 1 до n.

Переменная cur хранит текущее значение бонусов в дне i.

Для каждого i:

• cur += diff[i] — получили бонусы в дне i
• pref[i] = pref[i - 1] + cur — добавили их к общей префиксной сумме

В результате:

• cur — это значение массива бонусов в текущем дне
• pref[i] — сумма бонусов на днях от 1 до i

Шаг 3. Отвечаем на запросы

Для каждого запроса l, r выводим:

• pref[r] - pref[l - 1]

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

Докажем корректность по шагам.

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

Рассмотрим одну операцию: прибавить v ко всем дням от l до r.

После изменений:

• в diff[l] добавляется v
• в diff[r + 1] вычитается v

Когда мы потом считаем префиксную сумму массива diff, происходит следующее:

• для позиций меньше l эта операция никак не влияет;
• начиная с l, в накопленной сумме появляется +v;
• начиная с r + 1, это увеличение компенсируется -v.

Значит, ровно на отрезке [l, r] к значениям прибавляется v, а вне его — нет.

Так как все операции просто складываются, итоговая префиксная сумма diff даёт правильные значения бонусов для всех дней.

Почему pref правильно отвечает на суммы отрезков

Пусть после всех операций массив бонусов равен a[1], a[2], ..., a[n].

По построению:

• pref[i] = a[1] + a[2] + ... + a[i]

Тогда сумма на отрезке [l, r] равна:

• сумма от 1 до r минус сумма от 1 до l - 1

То есть:

• pref[r] - pref[l - 1]

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

5. Сложность

• Построение разностного массива: O(m)
• Восстановление массива и построение префиксных сумм: O(n)
• Ответы на запросы: O(q)

Итоговая сложность:

• O(n + m + q)

Память:

• O(n)

Важно использовать 64-битные целые числа, потому что ответы могут не помещаться в int.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0);

    for (int i = 0; i < m; i++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        diff[l] += v;
        if (r + 1 <= n) {
            diff[r + 1] -= v;
        }
    }

    vector<long long> pref(n + 1, 0);
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        pref[i] = pref[i - 1] + cur;
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << '\n';
    }

    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

diff = [0] * (n + 2)

for _ in range(m):
    l, r, v = map(int, input().split())
    diff[l] += v
    if r + 1 <= n:
        diff[r + 1] -= v

pref = [0] * (n + 1)
cur = 0
for i in range(1, n + 1):
    cur += diff[i]
    pref[i] = pref[i - 1] + cur

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])