Разбор задачи «Разностный массив»

1. Идея

Нужно обработать m команд вида: прибавить число v ко всем элементам на отрезке от l до r.

Если делать это напрямую, то одна команда может менять до n элементов, и тогда общее время в худшем случае будет O(n * m), что слишком медленно при n, m до 2 * 10^5.

Поэтому используется разностный массив.

Главная мысль такая:

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

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

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

Рассмотрим массив надбавок a[1..n], который изначально весь состоит из нулей.

Вместо того чтобы хранить сам массив a, будем хранить массив diff, где:

• diff[l] += v означает: начиная с позиции l, все следующие значения должны увеличиться на v;
• diff[r + 1] -= v означает: начиная с позиции r + 1, это увеличение больше не действует.

Тогда итоговое значение в позиции i получается как сумма всех diff[1] + diff[2] + ... + diff[i].

Пример

Пусть n = 5, и есть команда:

• прибавить 3 на отрезке [2, 4]

Тогда делаем:

• diff[2] += 3
• diff[5] -= 3

Массив diff станет таким:

• 0 3 0 0 -3

Теперь считаем префиксные суммы:

• позиция 1: 0
• позиция 2: 3
• позиция 3: 3
• позиция 4: 3
• позиция 5: 0

Именно это и нужно: 3 добавилось только на отрезке [2, 4].

3. Алгоритм

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

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

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

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

После выполнения:

• diff[l] += v
• diff[r + 1] -= v при наличии такой позиции

Посмотрим, как эта команда влияет на префиксную сумму в позиции i.

Случай 1: i < l

Префиксная сумма до позиции i ещё не включает diff[l], значит вклад этой команды равен 0.

Это верно: отрезок [l, r] ещё не начался.

Случай 2: l <= i <= r

Префиксная сумма уже включает diff[l] = +v, но ещё не включает diff[r + 1] = -v.

Значит вклад этой команды равен v.

Это верно: на всём отрезке [l, r] надо прибавить v.

Случай 3: i > r

Префиксная сумма включает и +v, и -v, они сокращаются.

Значит вклад равен 0.

Это верно: после позиции r действие команды заканчивается.

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

5. Сложность

• Обработка всех m команд: O(m)
• Восстановление итогового массива: O(n)

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

Память:

• массив diff размера 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;
        }
    }

    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        if (i > 1) {
            cout << ' ';
        }
        cout << cur;
    }
    cout << '\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

cur = 0
ans = []

for i in range(1, n + 1):
    cur += diff[i]
    ans.append(str(cur))

print(" ".join(ans))