я ищу способ найти в списке пропусков заданный элемент x, который является k-м в списке (перед ним есть k-1 элементы). Ожидаемое время алгоритма должно быть O (log K)
я нашел известный алгоритм, который принимает O (log n), но здесь это O (log K).
заранее спасибо
Вам нужно увеличить список пропусков, чтобы каждый узел имел количество элементов в своем «поддереве» (элементы в его нижнем правом положении до следующего узла на своем уровне).
Очень легко увидеть, что вы можете увеличить эту информацию, не изменяя сложности операций со списком.
Когда у вас есть эти метаданные, вам нужно перейти на уровень только до точки, где узел на следующем уровне уже слишком далеко вправо. В этот момент спуститесь на один уровень вниз.
Между прочим, эта проблема известна как динамическая статистика заказов посредством аугментации. Я никогда не видел этого со списками пропуска, но вы можете найти множество ссылок о том, как это сделать с другими упорядоченными деревьями, и это почти та же идея.
