Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.
===LCA===
Задача о наименьшем общем предке для двух вершин в дереве с <tex>n</tex> вершинами решается с помощью Heavyheavy-light декомпозиции за время . Воспользуемся основной идеей: декомпозиция разбивает все вершины дерева на вершинно-непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>O(\log{n})</tex>различных путей.
Мы можем проверять===Препроцессинг===Построим декомпозицию. Для каждой вершины, что вершина является предком другой вершины помимо её предка, будем хранить дополнительно следующие значения:# Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину. Тогда рассмотрим самый нижний путь (содержащий первую # Номер предка {{---}} начало пути от корня, ведущего в вершину) и посмотрим на его корень (самая высокая вершина в пути). Если эта вершина является предком второй # Номер вершины, то ответ где-то в этом которую выходит первое ребро пути, иначе рассмотрим следующий сверху путьведущего из предка в вершину. <br />Находится за <tex>O(1)</tex> при построении.
Когда мы определили путь===Вычисление LCA===Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>, пусть <tex>s</tex> {{---}} предок вершины <tex> u</tex>, а <tex> t</tex> {{---}} предок вершины <tex>v</tex>. Пусть вершина <tex>A</tex> {{---}} первая вершина пути из <tex>s</tex> в <tex>u</tex>, а <tex>B</tex> {{---}} первая вершина пути из <tex>t</tex> в <tex>v</tex>. Сравним вершины <tex>A</tex>, <tex>B</tex>: * <tex>A</tex> = <tex>B</tex>. <br />Или <tex>u</tex> лежит на пути от корня к <tex>v</tex>, или наоборот. За LCA примем ту вершину, которая лежит ближе к корню.* <tex>A</tex> <tex>\not=</tex> <tex>B</tex>.<br />Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения. Очевидно, что в результате придем или в котором содержится ответодну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы можем с помощью бинпоиска найти найдем LCA. ===Псевдокод=== <code> <font color=darkgreen>// Находит наименьшего общего предка вершин '''u''' и '''v'''</font> '''int''' lca('''int''' u, '''int''' v): <font color=darkgreen>// Проверяем вершины, в нём первую которые идут ребра из предков.</font> '''if''' (turn[u] == turn[v]): <font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font> '''if''' (dist[u] < dist[v]): '''return''' u '''else''': '''return''' v <font color=darkgreen>// Приблизимся к корню. Выбираем наиболее удаленную вершину.</font> '''if''' (dist[last[u]] > dist[last[v]]): '''return''' lca(last[u], v) '''return''' lca(last[v], u)</code> ===Ассимптотика===* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.* '''Препроцессинг''': Heavy-light декомпозиция строится за <tex>O(n)</tex>.* '''Запросы''': По свойству heavy-light декомпозиции, являющуюся предком второй на пути от вершинык корню мы сменим не более <tex>\log n</tex> путей. Эта вершина является ответомЗначит время выполнения запроса также <tex>O(\log n)</tex>.
Итого мы рассмотрели корень каждого пути за <tex>O(1)</tex>, а путей всего <tex>O(\log{n})</tex>. И в последнем пути один раз запустили бинпоиск, который отработал за <tex>O(\log{n})</tex>. Итоговая асимптотика <tex>O(\log{n})</tex>.
==Реализация==
Ниже будет приведена реализация запроса сумма на пути между любыми двумя вершинами в дереве без запросов модификации. Все запросы, сводящиеся к навешиванию дерева отрезков на пути из декомпозиции делаются похожим образом.
