Пример использования

Разберем такую задачу.

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

Каждое действие Папы Карло -- это либо забивание очередного гвоздика в точке с заданной координатой X, либо подсчет числа забитых гвоздиков на отрезке [X, Y]. Все координаты неотрицательные и не превосходят 10⁹, количество действий не превосходит 10⁵.

Буратино, узнав, в чем дело, решил помочь Папе Карло. Буратино подробно записал все действия Папы Карло в процессе изготовления вешалки и теперь хочет проверить расчеты по числу гвоздиков на разных интервалах, сделанные во время работы. Помогите ему в этом.

Требуется выдать результаты всех расчетов по числу гвоздиков на разных интервалах.

Решение. Если для каждой координаты хранить количество забитых в точку с этой координатой гвоздиков, то подсчет числа гвоздиков на отрезке [X, Y] является запросом rsq(X, Y) к соответствующему дереву Фенвика.

Однако при ограничениях на координаты до 10⁹ такой подход не проходит ни по требуемой памяти, ни по времени работы.

Решением проблемы в данном случае является так называемый «метод сжатия координат». Суть его состоит в следующем: отсортируем по координате все точки, встречающиеся во входном файле (их количество не превосходит 2 ^. 10⁵). Тут надо учитывать как точки, в которые забиваются гвоздики, так и концы отрезков, на которых производится подсчет числа гвоздиков.

Перенумеруем точки в соответствии с их позицией в отсортированном массиве. При этом точкам с одинаковыми координатами присвоим одинаковые номера.

После этого, заменив координаты всех точек их номерами, задачу можно решать с помощью дерева Фенвика, как это было предложено вначале, поскольку все номера не превосходят 2 ^. 10⁵.