Пусть у нас есть массив из N элементов, и мы хотим вычислить значение некого ассоциативного оператора над элементами этого массива от L до R включительно. Как известно, если построить дерево отрезков для массива, то мы сможем вычислять это значение за O(log N).
Дерево отрезков — это бинарное дерево, в котором каждой вершине соответствует какой-то отрезок массива, причем родительская вершина покрывает оба отрезка своих сыновей, а их отрезки в свою очередь не пересекаются; корень соответствует всему массиву целиком.
К чему я это говорю. Однажды я захотел поискать какие-нибудь англоязычные описания/реализации дерева отрезков и не смог найти ничего, что было бы предназначено для решения задачи, о которой я говорил в начале. Искал по словам «segment tree» и «interval tree». Если посмотреть статьи с этими названиями на английской Википедии, то мы обнаружим, что эти деревья используются для быстрого нахождения множества отрезков, которым принадлежит заданная точка. То есть задача совсем другая (или я просто не втыкаю, что это одно и то же).
И вот у меня вопрос. Как же по-английски называется та структура данных, которую мы называем деревом отрезков?
Пруф. Статья та же, но надо промотать чуть ниже.
Если я не баран, то в русском языке деревом отрезков называется немного другое -- когда ты можешь отвечать на вопрос "сколько интервалов покрывает заданную точку". Это частный случай того, что ты описал, где единственная разрешенная операция -- это прибавить единицу к интервалу.
Понятно, что алгоритм расширяется на любой ассоциативный оператор.
В таком виде (отвечая только на вопрос сколько отрезков пересекает точку) это называется на английском interval tree.
Мда, спать мне надо по ночам а не по инетам ползать %)
Вот еще такое же виденье segment trees, хотя родной язык автора тоже вызывает сомнения =)
UPD: А еще если в википедии заменить абстрактные pi на человеческие половинки на целых числах и не хранить всякое барахло в узлах, то оно и выйдет.
UPD2: Во, и note в вики на эту тему есть:
Another plus of the segment tree, is that it can easily be adapted to counting queries; that is, report the number of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in the canonical subsets, it can simply be stored an integer representing their amount. Such a segment tree uses linear storage, and requires an O(log n) query time, so it is optimal.
Переписал статью про дерево отрезков.
http://e-maxx.ru/algo/segment_tree
Постарался покрыть все известные мне приложения. Статья в альфа-версии, так что любые замечания приветствуются. Особенно хочется услышать про те применения дерева отрезков, которые я забыл упомянуть.
И да, чуть позже я повешу оглавление на статью, а то в ней легко заблудиться - стандартные h1/h2/h3 здесь плохо работают :)