Интервалы

[Iliya]

Помогите решить следующую задачу:
Есть множество интервалов. Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним. Подскажите в какую сторону гуглить/копать?

[Xaositect]

Дерево интервалов?

[ewert]

Iliya в сообщении #374200 писал(а):

Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним.

Что-то я пока не вижу вопроса. Всё равно ведь придётся все остальные интервалы перебрать -- и что может быть быстрее?...

[venco]

Быстрее вышеупомянутое interval tree.

[Cave]

Если $[a;b]$ именно задан и он один, то быстрее перебора всех интервалов точно не получится.
Если же набор интервалов фиксирован, а запросы разные, тогда да, дерево интервалов, оно же дерево отрезков.