Как обновлять отрезок и запрашивать точку через Фенвик на разностном массиве?
Нужны операции «прибавить v ко всем a[l..r]» и «узнать значение a[i]». Обычный Фенвик — это точечное обновление и префиксный запрос, то есть наоборот. Как развернуть его на «обновление отрезка + запрос точки»?
2 ответа
Трюк — разностный массив d, где a[i] = d[1] + d[2] + ... + d[i] (префиксная сумма разностей). Тогда прибавление v на [l, r] — это всего две точечные правки разностей:
d[l] += v(начиная с l всё выросло на v),d[r+1] -= v(после r эффект гасим).
А значение a[i] — это префиксная сумма d[1..i], которую Фенвик считает штатно.
struct BITRangeUpdate {
BIT b;
BITRangeUpdate(int n): b(n) {}
void rangeAdd(int l, int r, long long v){
b.update(l, v);
b.update(r + 1, -v); // r+1 не должно вылезти за n: завести BIT размера n+1
}
long long pointGet(int i){ return b.query(i); } // a[i]
};
Обе операции — O(log n), память O(n). Важно: BIT должен иметь размер хотя бы n+1, иначе update(r+1) при r=n выйдет за границу (либо отдельно проверяйте if (r+1 <= n)). Это самый дешёвый способ получить range-update/point-query без дерева отрезков.
Если потом понадобится ещё и запрос суммы на отрезке одновременно с обновлением отрезка — одного разностного BIT мало, нужны два BIT (range-update + range-query). Формула: держим B1 и B2, где префикс sum[1..i] = query(B1,i)*i - query(B2,i). При rangeAdd(l,r,v): B1.update(l,v); B1.update(r+1,-v); B2.update(l, v*(l-1)); B2.update(r+1, -v*r). Это расширение того же приёма; чаще на контесте именно оно и нужно.