Как построить массив разностей
Массив разностей — это полезная техника для эффективного применения множества обновлений на отрезках.
Вместо изменения каждого элемента на отрезке , мы обновляем лишь несколько позиций во вспомогательном массиве. После обработки всех обновлений мы восстанавливаем итоговый массив с помощью префиксных сумм.
Это позволяет выполнять каждое обновление на отрезке за времени.
Дан массив длины , определим его массив разностей diff так:
То есть diff[i] показывает, насколько меняется значение при переходе с позиции i - 1 на позицию i.
Если мы хотим прибавить к каждому элементу на отрезке , мы делаем:
diff[L] += xdiff[R + 1] -= x если Почему это работает?
L, все значения должны увеличиться на xR + 1, это увеличение должно прекратитьсяПосле применения всех обновлений мы восстанавливаем массив с помощью префиксных сумм:
diff[L] += xdiff[R + 1] -= x если это внутри массиваПусть:
Тогда массив разностей:
Теперь применим обновление: прибавить на отрезке .
Мы обновляем:
diff[2] += 3Нет необходимости применять diff[5] -= 3, потому что позиция 5 находится вне массива.
Теперь:
Восстановление массива:
Итоговый массив становится:
Вам дан массив из нулей и операций. Каждая операция прибавляет ко всем элементам на отрезке . После всех операций выведите итоговый массив.
vector<long long> diff(n + 2, 0);
diff[1] = a[1];
for (int i = 2; i <= n; i++) {
diff[i] = a[i] - a[i - 1];
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> diff(n + 2, 0);
for (int i = 1; i <= q; i++) {
int L, R;
long long x;
cin >> L >> R >> x;
diff[L] += x;
if (R + 1 <= n) {
diff[R + 1] -= x;
}
}
vector<long long> a(n + 1, 0);
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + diff[i];
cout << a[i] << " ";
}
cout << "\n";
return 0;
}