Найти k-ю единицу (k-й установленный элемент) спуском по дереву отрезков?
Массив из 0 и 1 (есть/нет элемент), бывают точечные обновления (поставить/убрать). Нужно отвечать на запрос «какая позиция у k-й единицы слева». Знаю, что дерево отрезков на сумму это умеет за O(log n) спуском. Как написать?
2 ответа
Держите дерево на сумму (количество единиц в поддереве). Спускаемся от корня: если в левом поддереве единиц >= k, k-я единица там; иначе вычитаем их количество из k и идём вправо.
int t[4*N]; // количество единиц в поддереве
int kth(int v, int tl, int tr, int k) { // 1-индексация k
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
if (t[2*v] >= k) return kth(2*v, tl, tm, k);
else return kth(2*v+1, tm+1, tr, k - t[2*v]);
}
Вызов: если t[1] < k, k-й единицы нет; иначе kth(1, 0, n-1, k). Точечное обновление (поставить/убрать единицу) — обычный update, меняющий значение листа на 0/1 и пересчитывающий суммы. Сложность: запрос k-й единицы O(log n), обновление O(log n), память O(n).
Это база для задач вроде «удалять каждого k-го по кругу» (Иосиф Флавий за O(n log n)) или поддержки порядковых статистик в динамическом множестве.
Та же техника, но если на отрезке хранятся произвольные счётчики (частоты), а не 0/1 — формула не меняется: в левом ребёнке суммарный счётчик t[2v], сравниваем с k. Это даёт порядковую статистику по частотам: «найти значение, у которого накопленная частота достигает k» — классический способ найти медиану/перцентиль в потоке, если значения дискретны и заранее известен их диапазон (тогда индекс листа = само значение).
Граabля индексации: следите за 1- vs 0-индексацией k. Если k считается с 1 (первая единица — k=1), условие t[2v] >= k; если с 0 — t[2v] > k. Перепутаете — будете стабильно мазать на 1 на границах.