Для оценки сложности цепочки инкрементов, пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число 010111, над каждой 1 лежит по 1 у.е., сколько потребуется элементарных действий для операции Increment?

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

• # Какая структура данных используется дополнительно в предобработке для offline LCA?
• # Каким должен быть размер блока для алгоритма ±1-RMQ, чтобы сократить сложность предобработки?
• # Если до вставки нового ребра E его вершины u и v находились в разных компонентах связности, какие действия предпринимают, чтобы сохранить структуру динамически связного графа?
• # Что делает операция Decrease-key для кучи?
• # За какое в среднем количество проб можно обнаружить хэш-функцию, не дающую коллизий для второго уровня схемы совершенного хэширования?