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

К чему я это говорю. Однажды я захотел поискать какие-нибудь англоязычные описания/реализации дерева отрезков и не смог найти ничего, что было бы предназначено для решения задачи, о которой я говорил в начале. Искал по словам «segment tree» и «interval tree». Если посмотреть статьи с этими названиями на английской Википедии, то мы обнаружим, что эти деревья используются для быстрого нахождения множества отрезков, которым принадлежит заданная точка. То есть задача совсем другая (или я просто не втыкаю, что это одно и то же).

И вот у меня вопрос. Как же по-английски называется та структура данных, которую мы называем деревом отрезков?