Почему дерево Фенвика индексируется с единицы и что сломается при индексации с нуля?
Во всех реализациях BIT массив с 1, и условие цикла i > 0. Что конкретно сломается, если я начну с нуля, как в обычном массиве? И как тогда хранить элемент с «логическим» индексом 0 из задачи?
2 ответа
Всё держится на lowbit(i) = i & -i. Для i = 0 имеем 0 & -0 == 0, то есть шаг становится нулевым. В query цикл for(; i>0; i -= i&-i) просто не зайдёт для i=0 (это ок — префикс длины 0 пуст). Но в update цикл for(; i<=n; i += i&-i) при i=0 даст i += 0 — бесконечный цикл, индекс 0 не имеет родителя в дереве. Поэтому позиция 0 в BIT «непредставима».
Решение стандартное: сдвиг на 1. Логический индекс k из задачи (0..n-1) кладём в BIT-позицию k+1 (1..n).
BIT bit(n); // позиции 1..n
bit.update(k + 1, v); // элемент k
long long pref = bit.query(k + 1); // сумма логических [0..k]
Сложность не меняется — O(log n). Если очень хочется 0-индексацию, есть варианты BIT с другим лейаутом, но они менее каноничны и легче ошибиться. На олимпиаде проще держать +1-сдвиг и не думать. Память O(n+1) — заводите вектор размера n+1.
Дополнение про координатное сжатие: когда значения большие (до 10^9), их всё равно сжимают в ранги. Делайте ранги сразу с 1, а не с 0 — тогда сдвиг встроен в само сжатие, и про индекс 0 можно забыть. Типичный приём: sort+unique, потом lower_bound(...) - begin + 1 как BIT-позиция.