Когда брать дерево Фенвика, а когда дерево отрезков — в чём практическая разница?
Обе структуры дают O(log n) на запрос и обновление. На контесте часто можно решить и тем, и другим. Как выбрать? Есть ли задачи, где Фенвик просто не сработает и нужен именно segment tree?
2 ответа
Короткое правило: Фенвик — для обратимых аддитивных операций (сумма, xor) и когда дорог каждый байт/наносекунда; дерево отрезков — для всего остального.
Берите Фенвик, когда:
- операция — сумма (или xor), запрос — префикс/отрезок через два префикса;
- нужна маленькая константа и короткий код (BIT в ~5 строк);
- нужна k-я статистика по частотам (binary lifting).
Берите дерево отрезков, когда:
- операция не обратима: min/max, gcd, «есть ли элемент», максимальный подотрезок — из префикса такое не вычесть;
- нужен lazy на присваивание/нетривиальное обновление отрезка;
- нужен спуск по дереву с условием (поиск первого элемента ≥ x на отрезке), сложные слияния узлов;
- хранится структура в узле (массив, сортированный список — merge sort tree).
По ресурсам: BIT — память O(n) с константой 1, segment tree — O(2n..4n); оба запроса O(log n), но у BIT константа меньше в ~2-3 раза. На жёстких TL по времени/памяти, где задача всё равно про сумму, Фенвик предпочтительнее. Если же операция min/max или нужен lazy — Фенвик честно не подходит, не пытайтесь.
Уточнение про min: Фенвиком можно делать префиксный min с обновлением «уменьшить значение» (только в одну сторону — point-update «новое ≤ старого», prefix-min query). Это частный полезный приём для некоторых DP. Но полноценный min на произвольном отрезке [l,r] с произвольными обновлениями — нет, потому что обратной операции у min нет, и query(l-1) не вычесть. Так что «BIT для min» — узкий частный случай, а не общее решение.