Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0 для 5 запросов?

Правильный ответ:

• # В алгоритме ±1-RMQ на блоки с минимумами какого размера разбивается исходная последовательность?
• # Для вершины с индексом i какие индексы будут у сыновей вершины?
• # Какие действия предпринимают для сохранения свойств красного черного дерева, если при операции вставки вершины x, x и y оказались красными, если y - родитель x, y - корень?
• # Если в splay-дереве есть операция, работающая за O(глубина вершины), можно ли ее ускорить до учетного логарифма, если да то как это сделать?
• # Отметьте утверждение, не относящееся к работе операции удаления для B-дерева