Как запрашивать сумму на отрезке [l, r] через дерево Фенвика двумя префиксами?
Фенвик умеет префиксную сумму [1..i]. А мне нужна сумма произвольного [l, r] с точечными обновлениями. Понимаю, что надо вычесть два префикса, но боюсь ошибиться на единицу с границами. Как правильно и за сколько?
2 ответа
Сумма [l, r] = query(r) - query(l-1), где query(i) — сумма префикса [1..i]. Это работает, потому что суммы аддитивны (групповая операция со взятием обратного — вычитанием).
long long rangeSum(BIT& bit, int l, int r){ // 1-индексация
return bit.query(r) - bit.query(l - 1);
}
Граница: при l = 1 выходит query(0), и цикл query корректно вернёт 0 (см. условие i>0) — отдельный if не нужен. Оба запроса — по O(log n), итого O(log n) на отрезочный запрос, точечное обновление тоже O(log n). Память O(n).
Ключевое ограничение: этот приём годится для обратимых операций (сумма, xor). Для min/max так нельзя — из min[1..r] нельзя «вычесть» min[1..l-1], нет обратной. Для min/max на отрезке берите дерево отрезков или Sparse Table (если массив статичен).
Частая ошибка на единицу: путают query(l-1) с query(l). Запомните: вычитаем префикс до l, то есть [1..l-1], чтобы l осталось внутри отрезка. Проверьте на l==r: query(r)-query(r-1) должно дать a[r] — если получили 0 или a[r-1], значит сдвиг неверный. Полезно сразу написать такой ассерт на маленьком массиве, прежде чем сдавать.