Heavy-light декомпозиция - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:27:35Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:49, 1 сентября 2022

2022-09-01T04:49:00Z

Mervap: /* LCA */

2018-05-09T19:16:00Z

‎LCA

Mervap в 21:09, 2 мая 2018

2018-05-02T21:09:27Z

Mervap в 13:42, 22 апреля 2018

2018-04-22T13:42:04Z

Mervap в 12:56, 22 апреля 2018

2018-04-22T12:56:11Z

Mervap в 00:37, 22 апреля 2018

2018-04-22T00:37:09Z

Mervap в 00:30, 22 апреля 2018

2018-04-22T00:30:04Z

Mervap в 00:12, 22 апреля 2018

2018-04-22T00:12:40Z

Mervap в 19:47, 21 апреля 2018

2018-04-21T19:47:45Z

← Предыдущая		Версия 16:27, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Heavy-light декомпозиция''' {{---}} техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).		'''Heavy-light декомпозиция''' {{---}} техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).
	==Описание задачи==		==Описание задачи==

← Предыдущая		Версия 04:49, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Heavy-light декомпозиция''' {{---}} техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).		'''Heavy-light декомпозиция''' {{---}} техника разбиения подвешенного дерева на множество путей для решения задач о запросах на пути в дереве (в том числе с модификациями).
	==Описание задачи==		==Описание задачи==

@@ Строка 58: / Строка 58: @@
 |statement=Пусть есть вершины <tex>u</tex> и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня дерева, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
-|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}(u, v)</tex> и <tex>\mathrm{LCA}(U, v)</tex> отличаются. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
+|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}(u, v)</tex> и <tex>\mathrm{LCA}(U, v)</tex> это разные вершины. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
 Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем <tex>1</tex> вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.

@@ Строка 37: / Строка 37: @@
 Докажем по отдельности корректность декомпозиции.
 # Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты.
-# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины <tex>v</tex> ведет более <tex>1</tex> тяжелого ребра в детей. Эти ребра относятся к разным путями, однако пути имеют хотя бы общее ребро {{---}} ребро из <tex>v</tex> в отца <tex>v</tex>. Более <tex>1</tex> тяжелого ребра из вершины идти не может, следовательно получили противоречие.
+# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины <tex>v</tex> ведет более <tex>1</tex> тяжелого ребра в детей. Эти ребра относятся к разным путями, однако пути имеют хотя бы общее ребро {{---}} ребро из <tex>v</tex> в отца <tex>v</tex>. Более <tex>1</tex> тяжелого ребра из вершины идти не может, следовательно, получили противоречие.
 # При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в <tex>2</tex> раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
 }}
@@ Строка 58: / Строка 58: @@
 |statement=Пусть есть вершины <tex>u</tex> и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня дерева, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
-|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
+|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}(u, v)</tex> и <tex>\mathrm{LCA}(U, v)</tex> отличаются. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
 Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем <tex>1</tex> вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
@@ Строка 64: / Строка 64: @@
 ====Препроцессинг====
-Построим heavy-light декомпозицию для данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
+Построим heavy-light декомпозицию данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
 # Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
 # Корень пути, на котором лежит вершина. <br /> Поскольку вершина может принадлежать нескольким путям, выберем тот, чья начальная вершина наиболее удалена от корня дерева. Имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.

@@ Строка 37: / Строка 37: @@
 Докажем по отдельности корректность декомпозиции.
 # Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты.
-# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело более чем одно тяжёлое ребро, чего быть не могло. Получили противоречие.
+# Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины <tex>v</tex> ведет более <tex>1</tex> тяжелого ребра в детей. Эти ребра относятся к разным путями, однако пути имеют хотя бы общее ребро {{---}} ребро из <tex>v</tex> в отца <tex>v</tex>. Более <tex>1</tex> тяжелого ребра из вершины идти не может, следовательно получили противоречие.
 # При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в <tex>2</tex> раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
 }}
@@ Строка 56: / Строка 56: @@
 {{Лемма
 |id=Лемма1
-|statement=Пусть есть вершины <tex>u</tex> и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
+|statement=Пусть есть вершины <tex>u</tex> и <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня дерева, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
 |proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
@@ Строка 92: / Строка 92: @@
    <font color=darkgreen>// Находит наименьшего общего предка вершин <tex>u</tex> и <tex>v</tex></font>
-   '''int''' lca('''int''' u, '''int''' v):
+   '''int''' lca('''int''' u, '''int''' v)
      <font color=darkgreen>// Проверяем вторые вершины путей, содержащих <tex>u</tex> и <tex>v</tex>.</font>
-     '''if''' (turn[u] == turn[v]):
+     '''if''' (turn[u] == turn[v])
        <font color=darkgreen>// Ответ найден, выберем ближайшую к корню.</font>
-       '''if''' (dist[u] < dist[v]):
+       '''if''' (dist[u] < dist[v])
          '''return''' u
-       '''else''':
+       '''else'''
          '''return''' v
-     <font color=darkgreen>// Рекурсивно запустимся от вершины, чей предок наиболее удален от корня.</font>
+     <font color=darkgreen>// Рекурсивно запустимся от вершины, чей предок наиболее удален от корня дерева.</font>
-     '''if''' (dist[last[u]] > dist[last[v]]):
+     '''if''' (dist[last[u]] > dist[last[v]])
        '''return''' lca(last[u], v)
      '''return''' lca(last[v], u)
@@ Строка 121: / Строка 121: @@
 Пример реализации запроса суммы на пути:
-  '''int''' query('''int''' u, '''int''' v):
+  '''int''' query('''int''' u, '''int''' v)
       '''int''' res = 0
       '''int''' root = корень пути, в котором находится u

@@ Строка 24: / Строка 24: @@
 Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в <tex>2</tex> вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
-'''Тяжёлые ребра''' (англ. ''heavy edge'') {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\frac{s(u)}{2}</tex>.
+'''Тяжёлые ребра''' (англ. ''heavy edge'') {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\dfrac{s(u)}{2}</tex>.
 '''Лёгкие ребра''' (англ. ''light edge'') {{---}} соответственно все остальные.
-Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\frac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
+Очевидно, что из вершины может выходить как максимум одно тяжёлое ребро, т.к. иначе у нас есть два поддерева по как минимум <tex dpi="150">\dfrac{s(u)}{2}</tex> вершин, а также сама вершина <tex>u</tex>. Итого <tex>s(u) + 1</tex> вершин, тогда как у нас всего <tex>s(u)</tex> вершин в поддереве.
 Теперь рассмотрим вершины, из которых не ведет вниз ни одно тяжёлое ребро. Будем идти от них вверх до корня или пока не пройдем легкое ребро. Получится какое-то множество путей. Утверждается, что полученная таким образом декомпозиция будет являться искомой и корректной.

@@ Строка 17: / Строка 17: @@
 </ul>
-Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex>) с помощью Heavy-light декомпозиции.
+Множество подобных запросов делаются за время за полином от логарифма (обычно <tex>O(\log^2{n})</tex>) с помощью heavy-light декомпозиции.
 ==Описание декомпозиции==
 [[Файл:Heavylight.png|thumb|right|800x280px|Пример разбиения. В вершинах указан размер поддерева.]]
 Необходимо составить такую декомпозицию дерева на множество рёберно-непересекающихся путей, что при прохождении от одной вершины до другой произойдет смена не более <tex>O(\log{n})</tex> путей из декомпозиции.
-Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в 2 вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
+Декомпозиция заключается в классификации всех рёбер дерева <tex>T</tex> в <tex>2</tex> вида: легкие и тяжёлые. Введём функцию <tex>s(v)</tex>, которая будет обозначать размер поддерева вершины <tex>v</tex>.
 '''Тяжёлые ребра''' (англ. ''heavy edge'') {{---}} ребра <tex>(u, v)</tex> такие, что <tex>s(v) \geqslant</tex> <tex dpi="150">\frac{s(u)}{2}</tex>.
@@ Строка 38: / Строка 38: @@
 # Все рёбра покрыты путями. <br>Есть два типа вершин: те, из которых ведёт ровно одно тяжёлое ребро и те, из которых не ведёт ни одного тяжёлого ребра. Для первого типа вершин мы дойдем до них некоторым путём через тяжёлое ребро снизу по определению выбора путей, а лёгкие рёбра ведущие из неё возьмем как последние рёбра в соответствующих путях. Для второго типа вершин мы по определению выбора путей возьмем их как начальные и пойдем вверх. <br>Таким образом все рёбра будут покрыты.
 # Все пути не пересекаются. <br>Докажем от противного. Пусть мы взяли какое-то ребро дважды. Это значит, что из какой-то вершины вело более чем одно тяжёлое ребро, чего быть не могло. Получили противоречие.
-# При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в 2 раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
+# При прохождении пути от вершины <tex>v</tex> до вершины <tex>u</tex> произойдет смена не более, чем <tex>O(\log{n})</tex> путей. <br>Докажем эквивалентный факт, что при пути от любой вершины до корня мы сменим не более, чем <tex>O(\log{n})</tex> путей. Рассмотрим лёгкое ребро. Заметим, что проход вниз по такому ребру уменьшает размер поддерева как минимум в <tex>2</tex> раза. Но смена пути может произойти только при переходе по лёгкому ребру. Таким образом мы сменим не более <tex>O(\log{n})</tex> путей.
 }}
-Существует вариант Heavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
+Существует вариант heavy-light декомпозиции на вершинно-непересекающихся путях. Чтобы получить такой путь нужно всего-лишь выкинуть последнее ребро из всех путей в рёберно-непересекающейся декомпозиции. Это может быть удобно при решении задач, где веса находятся не на рёбрах, а на вершинах и соответствующие запросы также делаются на вершинах.
 ==Применение==
@@ Строка 60: / Строка 60: @@
 |proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
-Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем 1 вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
+Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем <tex>1</tex> вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
 }}

@@ Строка 48: / Строка 48: @@
 Классическая задача о сумме на пути в дереве с <tex>n</tex> вершинами может быть решена с помощью Heavy-light декомпозиции за время <tex>O(\log^2{n})</tex>. Возможны модификации веса.
-Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>LCA(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за <tex>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.
+Построим [[Дерево отрезков. Построение|дерево отрезков]] над каждым путём. Рассмотрим запрос <tex>sum(u, v)</tex>. Найдем вершину <tex>c</tex>, которая является <tex>\mathrm{LCA}(u, v)</tex> (например с помощью [[Метод двоичного подъема|двоичного подъема]]. Мы разбили запрос на два: <tex>(u, c)</tex> и <tex>(c, v)</tex>, на каждый из которых можно легко ответить разбив его на множество путей из декомпозиции и ответив на каждый путь из этого множества по отдельности за <tex>O(\log{n})</tex> с помощью дерева отрезков на этом пути. Всего таких путей нужно будет рассмотреть <tex>O(\log{n})</tex>. Итого мы способны решить эту задачу за время <tex>O(\log^2{n})</tex>.
 Хоть это и не самый эффективный способ для решения этой задачи, но можно заметить, что навесив дерево отрезков на каждый путь мы способны отвечать на любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде (операции, поддерживаемые деревом отрезков), такие как: сумма на пути, максимум на пути, количество рёбер на пути, удовлетворяющих какому-то свойству.
@@ Строка 56: / Строка 56: @@
 {{Лемма
 |id=Лемма1
-|statement=Пусть есть две вершины <tex>u</tex>, <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня, чем <tex>V</tex>, то <tex>LCA(u, v) </tex> = <tex>LCA(U, v)</tex>.
+|statement=Пусть есть две вершины <tex>u</tex>, <tex>v</tex>, лежащие на разных путях. При этом <tex>U</tex>, <tex>V</tex> — корни путей, на которых они лежат. Если <tex>U</tex> более удален от корня, чем <tex>V</tex>, то <tex>\mathrm{LCA}(u, v) = \mathrm{LCA}(U, v)</tex>.
-|proof=Пусть пути не пересекаются. Предположим, что LCA не равны. Значит существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся LCA. Но LCA должен принадлежать двум путям. Однако пути на пересекаются. Тем самым пришли к противоречию.
+|proof=Допустим, пути не пересекаются. Предположим, что <tex>\mathrm{LCA}</tex> не равны. Тогда существует вершина, на пути от <tex>u</tex> к <tex>U</tex>, являющаяся <tex>\mathrm{LCA}</tex>. Значит <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, но по предположению пути не пересекаются. Тем самым пришли к противоречию.
-Рассмотрим случай, когда пути пересекаются. Пути не могут пересекаться более, чем в одной вершине. В данном случае корень одного из путей является вершиной другого. LCA должен принадлежать двум путям, значит именно этот корень и будет LCA.
+Теперь рассмотрим случай, когда пути пересекаются. Пути не могут совпадать более, чем в одной вершине, так как построенная декомпозиция является реберно-непересекающейся. При этом корень одного из путей является вершиной другого (либо корни совпадают, что равносильно), поскольку в противном случае пути пересекаются в более чем 1 вершине, что противоречит предыдущему условию. <tex>\mathrm{LCA}</tex> должен принадлежать двум путям, значит именно этот корень и будет <tex>\mathrm{LCA}</tex>.
 }}
 ====Препроцессинг====
-Построим декомпозицию. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
+Построим heavy-light декомпозицию для данного нам дерева. Для каждой вершины, помимо её предка, будем хранить дополнительно следующие значения:
 # Расстояние до корня дерева. <br />Вычисляется за <tex>O(1)</tex> с помощью времен входа\выхода в каждую вершину.
-# Корень пути, на котором лежит текущая вершина. <br />Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева. Очевидно, что имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.
+# Корень пути, на котором лежит вершина. <br />Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева. Очевидно, что имея разбиение на пути, найти корень можно за <tex>O(1)</tex>.
 # Вторая вершина этого пути. <br />Аналогично, находится за <tex>O(1)</tex> при построении.
 ====Вычисление LCA====
-Пусть требуется найти LCA для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex>, <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то мы нашли ответ: LCA будет та, которая ближе к корню, т.е расстояние от корня до которой минимально.  Очевидно, что если расстояние от <tex>u</tex> до корня меньше, чем расстояние от <tex>v</tex> до корня, то <tex>u</tex> является предком <tex>v</tex>, а не наоборот.
+Найдем <tex>\mathrm{LCA}</tex> для двух вершин. Для этого будем рекурсивно подниматься от этих вершин в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>u</tex> и <tex>v</tex>. Заметим, что если эти вершины лежат на одном пути, то ответ {{---}} это такая вершина (<tex>u</tex> или <tex>v</tex>), которая находится ближе к корню. Очевидно, что если расстояние от корня до <tex>u</tex> меньше, чем расстояние до <tex>v</tex>, то <tex>u</tex> является предком <tex>v</tex>. Иначе, наоборот.
-Для проверки этого условия недостаточно знать только корни путей. Потому что бесконечно большое количество путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.
+Для проверки этого условия недостаточно знать только корни путей, потому что несколько путей могу иметь общий корень. Но любые два пути пересекаются не более чем в одной вершине. Воспользуемся этим фактом.
 Пусть <tex>a</tex> и <tex>b</tex> {{---}} вторые вершины путей, содержащих вершины <tex>u</tex> и <tex>v</tex> соответственно. Важно заметить, что любая вершина, помимо корня дерева является некорневой вершиной какого-либо другого пути, поэтому такие <tex>a</tex> и <tex>b</tex> всегда существуют.
-* Заметим, что если <tex>a</tex> = <tex>b</tex>, то или <tex>u</tex> лежит на пути от корня к <tex>v</tex>, или наоборот. Этот случай мы уже рассмотрели ранее.
+* Заметим, что если <tex>a</tex> = <tex>b</tex>, то <tex>u</tex> и <tex>v</tex> лежат на одном пути. Этот случай мы уже рассмотрели ранее.
-* Если это не так, то вершины лежат на разных путях. По лемме, т.к пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.
+* Если это не так, то вершины лежат на разных путях. По лемме, так как пути реберно не пересекаются, то ответ не изменится, если вместо одной из вершин взять корень того пути, на котором она лежит. Эту операцию будем производить с той вершиной, чей предок наиболее удален от корня. Рекурсивно запустимся от выбранной и оставшейся вершин.
+Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем <tex>\mathrm{LCA}</tex>.
 ====Псевдокод====