Сколько страниц у индекса
База данных строит индекс — B+-дерево, у которого все ключи лежат в листьях, а страницы выше только направляют поиск. Ключи приходят по одному и попадают в лист, к которому их приводит спуск от корня: это последний по порядку лист, у которого первый ключ не больше нового (или самый первый лист, если новый ключ меньше всех). В листе помещается не больше C ключей. Когда в лист приходит (C + 1)-й ключ, лист делится.
half— пополам: в старом листе остаются первые ⌊(C + 1)/2⌋ ключей, остальные уходят в новый лист сразу справа от него.edge— так же, но с одним исключением, как в SQLite: если новый ключ больше всех ключей индекса, старый лист остаётся полным, а новый ключ один открывает новый лист справа.
Сколько листьев будет у индекса, когда все ключи вставлены? Второй и третий тесты — индекс по словам «Войны и мира»: ключи приходят в порядке текста, ключ — место пары «слово, номер в тексте» по алфавиту. Четвёртый и пятый — индекс по времени землетрясений из каталога USGS: ключи приходят по возрастанию.
Вход
В первой строке n, C и правило деления (1 ≤ n ≤ 2·10⁵, 2 ≤ C ≤ 1000, правило — half или edge). Во второй — n разных целых ключей от 0 до 10⁹ в порядке вставки.
Выход
Число листьев.
Примеры
Пример 1
10 4 half 1 2 3 4 5 6 7 8 9 10
4
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Страницы над листьями только выбирают, в какой лист спуститься. Зависит ли этот выбор от того, как устроены верхние этажи? Что достаточно знать о листьях, чтобы найти нужный?
2Подсказка 2
Ключи не удаляются, поэтому первый ключ листа после деления никогда не уменьшается ниже разделителя, который за ним закрепился. Найти лист можно двоичным поиском по первым ключам листьев.
3Идея
Держим листья в списке по порядку и рядом — список их первых ключей. Новый ключ ищет свой лист двоичным поиском по первым ключам, встаёт в лист на своё место, а при переполнении лист делится, и новый лист вставляется в оба списка сразу за старым. Это и есть B-дерево из двух этажей: список первых ключей играет роль всех верхних страниц сразу.
4Разбор
Почему верхние этажи не важны. Разделитель, который поднимается в родителя при делении, — первый ключ нового правого листа, и спуск отправляет в этот лист ровно ключи не меньше разделителя. Ключи только добавляются, значит, первый ключ правого листа так и остаётся равен разделителю, а первый ключ самого левого листа — наименьшему ключу. Поэтому «лист, к которому приведёт спуск» — это последний лист с первым ключом не больше нового, как бы ни делились внутренние страницы.
Правило edge проверяет новый ключ против наибольшего во всём индексе, а не в листе: такой ключ всегда приходит в последний лист. Вставка в середину списков сдвигает хвост, но листьев в C/2 раз меньше, чем ключей, а сдвиг — быстрая копия памяти.
Числа тестов о том же, о чём статья. На словах романа в порядке текста при C = 128 листья заполнены на 61 %, хуже теоретических 69 % для случайного порядка: позиции каждого слова приходят по возрастанию. На времени землетрясений при half листья заполнены ровно наполовину, при edge — почти целиком, и листьев вдвое меньше.
4+Решение
5Сложность
O(n log n) на поиск листа и O(C) на вставку в лист; вставка в списки листьев — O(n/C) сдвиг, редкий и быстрый. Память O(n).
6Типичные ошибки
edgeпо наибольшему в листе. Тогда полный лист в середине индекса не делится пополам, а отрезает себе новый лист из одного ключа, и дальше всё идёт иначе: на третьем, седьмом и десятом тестах число листьев не сходится.- Не тот лист для наименьшего ключа. Ключ меньше всех идёт в самый первый лист, и его первый ключ меняется.
- Поиск листа перебором. На шестом тесте листьев больше семнадцати тысяч, и перебор на каждый ключ — сотни миллионов шагов на тест.