Структура данных для ведения номеров

Question

Пожалуйста, предложите структуру данных для ведения чисел таким образом, чтобы я мог ответить на следующие запросы -

Найти (int n) - O (log (n))

Число счетачисел меньше k = O (log (n))

Вставка - O (Log (n))

Это не домашняя работа, а меньшая проблема, с которой я сталкиваюсь, чтобы решить большуюодин - Количество студентов с лучшими оценками и более низким рангом джипа

У меня есть хотя бы дерево avl с поддержкой количества узлов в поддереве на каждом узле. Но я не знаю, как поддерживать этосчитать на каждом узле, когда выполняется вставка и выполняется повторная балансировка.

Answer 1

Я бы тоже попробовал использовать AVL Tree. Не углубляясь в это, я не думаю, что это будет слишком сложно добавить. В случае дерева AVL вам всегда необходимо знать глубину каждого поддерева для каждого узла (или, по крайней мере, коэффициент балансировки). Так что не должно быть слишком сложно распространять размер поддеревьев. В случае ротации вы точно знаете, где приземлится каждый узел и каждое поддерево, поэтому для тех узлов, которые вращаются, это должен быть простой пересчет.

Answer 2

Поиск в двоичном дереве - это O (log (n)), вставка тоже.Если вы сохраняете размер поддерева в узле:

• , вы можете вернуться с успешной вставки в поддерево, увеличив счетчик узла;
• при удалении того же самого.

Таким образом, размер поддерева подобен находке, O (log (n)).

Answer 3

Посмотрите на различные варианты структур данных кучи, например, здесь .