Как искать k-ю порядковую статистику по дереву Фенвика за O(log n) (binary lifting)?
BIT хранит количество элементов по значениям (частоты). Нужно отвечать на запрос «какое значение стоит на k-й позиции по возрастанию» (k-я порядковая статистика). Наивно — бинпоиск + query = O(log²n). Слышал, что можно за один O(log n) прямо по структуре дерева. Как?
2 ответа
Да, есть binary lifting по Фенвику — спуск по битам без вложенного бинпоиска. Идём от старшего бита к младшему, пробуя «прыгнуть» вперёд на степень двойки, пока накопленная сумма частот не превышает k.
// t[] — BIT частот, LOG = floor(log2(n))
int findKth(vector<long long>& t, int n, long long k){
int pos = 0; long long rem = k;
for (int pw = 1 << LOG; pw; pw >>= 1) {
if (pos + pw <= n && t[pos + pw] < rem) {
pos += pw;
rem -= t[pos]; // используем уже посчитанный блок
}
}
return pos + 1; // 1-индексированное значение/ранг
}
Почему работает: t[pos+pw] хранит сумму блока длины pw сразу за pos (так устроен Фенвик), поэтому каждый бит позиции мы решаем за O(1), не вызывая query. Условие t[pos+pw] < rem (строго) даёт «нижнюю границу»: после цикла pos+1 — наименьшее значение, чей префикс ≥ k. Сложность O(log n) на запрос вместо O(log²n), память O(n).
Это и есть быстрый способ сделать «k-я статистика в динамическом мультимножестве»: вставка/удаление — update(val, ±1), k-я — findKth. Часто заменяет policy-tree (ordered_set).
Тонкость с < vs <=: если хотите наименьшее значение с префиксом строго ≥ k (классическая k-я статистика, k с 1), берите строгое t[pos+pw] < rem. Если же ищете «последнюю позицию с префиксом ≤ k» — условие меняется. Проверьте на крайних k=1 и k=общее число. И заметьте: цикл должен стартовать с pw = наибольшая степень двойки ≤ n; если взять больше n — первые проверки просто отсекутся условием pos+pw<=n, но лучше LOG считать честно, чтобы не терять корректность на n, не равных степени двойки.