Подсчитать количество перекрывающихся интервалов при ограничениях памяти?

Question

Мне нужно вести список интервалов в виде кортежа (x, y) и отвечать на запросы, которые запрашивают общее количество интервалов, перекрывающих точку p.Если нет ограничений памяти, я думаю, что эффективным решением было бы использование дерева сегментов, которое требует пространства O (nlogn), путем хранения дополнительной информации в каждом узле и использования метода ленивого обновления.

Я попытался сделать это, используядерево интервалов, но время выполнения запроса зависит от количества сообщаемых интервалов.

Можем ли мы сделать что-то лучше, чем это, при ограничениях памяти?

Answer 1

Лучшим решением являются деревья Фенвика (также известные как деревья двоичных индексов), у которых есть ограничение: вы можете либо обновить диапазон и запросить точку, либо обновить точку и запросить диапазон. Поскольку вы обновляете диапазоны и запрашиваете точку, Fenwick Tree является хорошим решением.

У них есть поиск O (log N) и используется пространство O (N), где N - диапазон значений x и y. Кроме того, обновления O (журнал N) тоже.

Лучше всего то, что они тривиальны для кода. Гораздо тривиальнее, чем деревья сегментов.

Вот замечательный учебник: TopCoder - деревья двоичных индексов