1. Идея

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

Если делать каждую надбавку напрямую по всем элементам от l до r, то одно обновление может занимать до O(n), а все вместе — до O(n * m), что слишком медленно.

Здесь подходит разностный массив:

• чтобы прибавить v ко всем элементам на отрезке [l; r],
• достаточно сделать:
  • diff[l] += v
  • diff[r + 1] -= v, если r + 1 не выходит за границы.

После этого итоговый массив восстанавливается обычными префиксными суммами.

Тогда все массовые обновления обрабатываются быстро, а ответы на запросы потом получаются мгновенно.

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

Наблюдение 1

Если есть массив a, то его разностный массив diff можно понимать так:

• diff[i] показывает, как изменилось значение при переходе от позиции i - 1 к позиции i.

Тогда сам массив a можно восстановить так:

• a[1] = diff[1]
• a[2] = a[1] + diff[2]
• ...
• то есть a[i] — это префиксная сумма массива diff.

Наблюдение 2

Обновление на отрезке [l; r] можно записать очень компактно:

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

Значит:

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

Когда потом посчитаем префиксные суммы, прибавка v автоматически распространится на весь отрезок от l до r.

Наблюдение 3

Так как после всех обновлений идут только точечные запросы, удобнее сначала полностью восстановить итоговый массив a, а потом просто выводить a[i] для каждого запроса.

3. Алгоритм

1. Считать n и m.
2. Создать массив diff размера n + 2, заполненный нулями.
   • Размер n + 2 удобен, чтобы безопасно обращаться к r + 1.
3. Для каждой из m надбавок:
   • считать l, r, v;
   • выполнить diff[l] += v;
   • если r + 1 <= n, выполнить diff[r + 1] -= v.
4. Построить итоговый массив a размера n + 1:
   • a[0] = 0;
   • для i от 1 до n:
     • a[i] = a[i - 1] + diff[i].
5. Считать q.
6. Для каждого запроса:
   • считать позицию i;
   • вывести a[i].

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

Докажем, что алгоритм действительно правильно считает итоговое значение в каждой позиции.

Рассмотрим одно обновление: прибавить v ко всем элементам на отрезке [l; r].

После действий

• diff[l] += v
• diff[r + 1] -= v

при вычислении префиксных сумм получится следующее:

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

Итак, вклад одного такого обновления равен:

• 0 вне отрезка [l; r],
• v на всём отрезке [l; r].

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

Именно это и получится после вычисления префиксных сумм массива diff.

Значит, массив a, который мы строим, содержит точные итоговые значения после всех массовых надбавок. Тогда ответ на запрос в позиции i — это просто a[i].

5. Сложность

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

Итоговая сложность: O(n + m + q)

По памяти:

• diff хранит O(n)
• a хранит O(n)

Итоговая память: O(n)

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 k = 0; k < m; k++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        diff[l] += v;
        if (r + 1 <= n) {
            diff[r + 1] -= v;
        }
    }

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

    int q;
    cin >> q;
    for (int j = 0; j < q; j++) {
        int i;
        cin >> i;
        cout << a[i] << '\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

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

q = int(input())
for _ in range(q):
    i = int(input())
    print(a[i])