Как сделать Фенвик с обновлением отрезка И запросом суммы на отрезке (два BIT)?
Нужны сразу обе операции: «прибавить v к a[l..r]» и «сумма a[l..r]». Знаю, что один разностный BIT даёт только точечный запрос. Слышал про два BIT и формулу с умножением на индекс — можете вывести её и дать рабочий код?
2 ответа
Идея: работаем с разностным массивом d, тогда префикс S(i) = sum a[1..i] = sum_{k=1..i} d[k]*(i - k + 1). Раскрываем: S(i) = (i+1)*sum d[k] - sum k*d[k]. Заводим два Фенвика: B1 накапливает d[k], B2 накапливает k*d[k].
struct RangeBIT {
int n; BIT b1, b2;
RangeBIT(int n): n(n), b1(n+1), b2(n+1) {}
void _add(BIT& b, int i, long long v){ b.update(i, v); }
void rangeAdd(int l, int r, long long v){
_add(b1, l, v); _add(b1, r+1, -v);
_add(b2, l, v*(l-1)); _add(b2, r+1, -v*r);
}
long long pref(int i){ return b1.query(i)*(long long)i - b2.query(i); }
long long rangeSum(int l, int r){ return pref(r) - pref(l-1); }
};
Вывод коэффициентов в rangeAdd: чтобы префикс-формула давала верный вклад v на [l,r], в B2 кладём v*(l-1) в l и -v*r в r+1 — это компенсирует индексные множители на краях. Обе операции — O(log n), память O(n). Это полная замена «дерева отрезков с lazy на прибавление» там, где операция — сумма; константа у BIT заметно меньше.
Грабли с переполнением: v*(l-1) и pref(i) = b1.query(i)*i легко вылетают за long long, если v до 10^9, а i до 10^6 — произведение до 10^15, накопленное по многим обновлениям ещё больше. Считайте битовую ширину заранее; иногда нужен __int128 для промежуточных. И не забудьте размер BIT n+1, иначе r+1 при r=n — выход за границу.