И да, если у вас элементы последовательности — целые числа, то можете посмотреть в сторону vEB-дерева. Вообще-то, есть еще более эффективные структуры, чем эта, но относительно деревьев отрезков и деревьев поиска она уже работает быстрее. Но лучше это всё проверить на практике, конечно.
