Загрузка по порядку
Журнал событий получает записи с номерами 1, 2, 3, … строго по порядку и строит по номеру индекс — АВЛ-дерево с теми же правилами, что в статье: новый ключ становится листом, а потом узлы на пути к корню пересчитывают высоты и при перекосе в два этажа делают одиночный или двойной поворот. Администратор хочет знать заранее, не загружая журнал: какой высоты будет индекс после n записей, сколько всего перебалансировок сделают вставки и сколько сравнений будет стоить поиск записи номер k, то есть на какой глубине она окажется (у корня глубина 1).
Второй и шестой тесты — индекс каталога USGS из 19 073 землетрясений силой от 5 за 2015–2025 годы, загруженного по порядку времени; во втором спрашивают о сильнейшем землетрясении каждого года.
Вход
В первой строке q (1 ≤ q ≤ 10⁵) — число вопросов. Дальше q строк n k (1 ≤ k ≤ n ≤ 10¹⁸).
Выход
На каждый вопрос — строку из трёх чисел: высоту дерева после вставки ключей 1, 2, …, n по порядку в пустое АВЛ-дерево, общее число перебалансировок за все эти вставки (двойной поворот — одна перебалансировка) и глубину ключа k.
Примеры
Пример 1
5 1 1 7 4 8 8 12 5 12 11
1 0 1 3 4 1 4 4 4 4 8 4 4 8 3
Пример 2
13 19073 1088 19073 3153 19073 4320 19073 5808 19073 7258 19073 9066 19073 11014 19073 13130 19073 13811 19073 15440 19073 17977 19073 1 19073 19073
15 19058 8 15 19058 14 15 19058 9 15 19058 10 15 19058 13 15 19058 13 15 19058 13 15 19058 14 15 19058 15 15 19058 11 15 19058 15 15 19058 14 15 19058 15
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Построить дерево из 10¹⁸ узлов нельзя, но можно построить маленькие. Вставьте по порядку ключи до 20–30 листингом из статьи и выпишите для каждого n правую ветку от корня: корень, его правый ребёнок, его правый ребёнок и так далее. Что висит у этих узлов слева?
2Подсказка 2
Поворот не меняет высоту поддерева, в котором случился, — это теорема из статьи. Значит, высота дерева растёт только на вставках без поворота. Листинг статьи показывает, что на возрастающих ключах без поворота обходятся ровно 1-я, 2-я, 4-я, 8-я, … вставки. Как это связано с двоичной записью n?
3Подсказка 3
Слева у узлов правой ветки висят идеальные деревья. Запишите n в двоичной системе и сравните высоты этих идеальных деревьев с цифрами записи.
4Идея
Дерево, выросшее из ключей 1, …, n, — двоичная запись числа n. Пусть n = 1b₁b₂…bH−1 в двоичной системе, H — число цифр. Тогда правая ветка от корня состоит из H узлов v₁, …, vH, последний из них лист, а слева у vj (при j < H) висит идеальное дерево высоты aj = H − 1 − j + bj. Вставка следующего ключа — прибавление единицы к n: если в записи есть нуль, ровно один поворот, если нет — рост высоты без поворотов. Отсюда высота H, перебалансировок n − H, а глубину ключа находит проход по правой ветке.
5Разбор
Почему так устроено. Докажем утверждение индукцией по n. При n = 1 дерево — один лист, H = 1. Заметим сначала, что поддерево с корнем vj имеет высоту H − j + 1: слева у него идеальное дерево высоты не больше H − j, справа — остаток ветки высоты H − j. Баланс vj (левая высота минус правая) равен bj − 1, то есть 0 или −1, и дерево действительно АВЛ-дерево.
Вставим ключ n + 1. Он больше всех и становится правым ребёнком листа vH. Пусть в записи n есть нуль и m — место последнего нуля: bm = 0, а все цифры после него — единицы. Поднимаемся от vH: у каждого vj с j > m баланс был 0, правая ветка выросла — баланс −1, высота выросла, идём дальше. У vm баланс был −1, и правая ветка выросла до H − m + 1 при левой H − m − 1: перекос. Правый ребёнок vm+1 перевешивает вправо (слева у него идеальное дерево высоты H − m − 1, справа теперь H − m), это случай RR — один поворот налево. После поворота vm получает слева и справа два идеальных дерева высоты H − m − 1 и сам становится корнем идеального дерева высоты H − m, а vm+1 встаёт на его место. Высота поддерева прежняя, выше ничего не меняется.
Новая правая ветка: v₁, …, vm−1, vm+1, …, vH и новый лист — снова H узлов. У n + 1 цифры до места m те же, на месте m стоит 1, дальше нули. Проверим формулу: на месте m теперь узел с идеальным деревом высоты H − m = H − 1 − m + 1; на месте p > m стоит бывший vp+1 с деревом высоты H − 1 − (p + 1) + 1 = H − 1 − p + 0; последний — лист. Всё сходится.
Если же n = 2H − 1 и все цифры — единицы, все узлы ветки были ровными, каждый получает баланс −1 и становится выше, поворотов нет, и высота дерева растёт до H + 1. Ветка удлиняется новым листом, а n + 1 = 10…0 с H нулями: высоты слева H − j = (H + 1) − 1 − j + 0, формула верна.
Ответы. Высота — H, число двоичных цифр n. Перебалансировка случается на каждой вставке, кроме тех, где новое n — степень двойки, а таких среди 1, …, n ровно H: всего n − H. Для 19 073 записей это 15 и 19 058 — столько же насчитал листинг статьи. Ключ узла vj на единицу больше всех ключей левее него: vj = vj−1 + 2aj (с v₀ = 0). Идём по ветке, пока k > vj. Если k = vj, глубина j. Иначе k лежит в идеальном дереве слева от vj с ключами vj−1 + 1, …, vj − 1; пусть m = k − vj−1. В идеальном дереве высоты a с ключами 1, …, 2a − 1 корень — 2a−1, и ключ m лежит на глубине a минус число нулей в конце двоичной записи m. Ответ — j + aj − (нули в конце m).
5+Решение
6Сложность
O(log n) на вопрос: ветка из H ≤ 60 узлов. На случайных k проход обычно кончается на первых узлах: в левом дереве корня не меньше 2H−2 − 1 ключей — почти четверть всех, а часто больше половины.
7Типичные ошибки
- Логарифм в плавающей точке.
ceil(log2(n + 1))при n = 253 и больше считает n + 1 без последней единицы: для n = 2⁶⁰ получается 60 вместо 61. Число цифр даётn.bit_length()в Python иbits.Len64в Go — точно. - Честная вставка. Даже на 10⁶ записей она работает, но на 10¹⁸ — никогда.
- Высота «как у идеального дерева» без доказательства глубин. Высота и число поворотов угадываются по маленьким примерам, а глубина конкретного ключа зависит от формы дерева целиком: без формулы для левых поддеревьев её не найти.
- Переполнение. Ключи до 10¹⁸ помещаются в 64-битное целое, но сумма степеней двойки по ветке — тоже ключ, она не больше n; складывать в 32 битах нельзя.