Описание тега range-tree
Дерево диапазонов - это структура данных, которая позволяет выполнять быстрые запросы диапазона, такие как [4, 5] x [-2, 0]. Используйте для вопросов, связанных с внедрением / изучением этого дерева.
Источники Википедии:
Дерево диапазонов на наборе одномерных точек - это сбалансированное двоичное дерево поиска в этих точках. Точки, хранящиеся в дереве, хранятся в листьях дерева; каждый внутренний узел хранит наибольшее значение, содержащееся в его левом поддереве. Дерево диапазонов по набору точек в d-измерениях - это рекурсивно определенное многоуровневое двоичное дерево поиска. Каждый уровень структуры данных представляет собой двоичное дерево поиска по одному из d-измерений. Первый уровень - это двоичное дерево поиска по первой из d-координат. Каждая вершина v этого дерева содержит связанную структуру, которая является (d-1)-мерным деревом диапазонов по последним (d-1)-координатам точек, хранящихся в поддереве v.