Изменения

В каждой вершине дерева хранится <tex>x_{mid}</tex>, ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают <tex>x_{mid}</tex>. Рассмотрим Необходимо рассмотреть два симметричных случая. НапримерПокажем, что делать в одном из них. Пусть, например, <tex>q_x>x_{mid}</tex>. Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать <tex>q_x</tex>). Аналогично разбирается случай <tex>q_x < x_{mid}</tex>.