Изменения

поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b</math>, такой что <tex>b_i = 0</tex>, если в i-м городе принимает госпиталь и <tex>b_i = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь {{---}} делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий ближайший госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей:

* (<tex>O(n \cdot log(n)</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно одновременно и бинарный поиск, и спуск/подъем по дереву.

'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,\dots, t_k</tex>, таких что для каждого <math>i</math>: <tex>|t_i| \leqslant \dfrac{n}{2}</tex>, т.е. то есть размер каждого поддерева не превосходит половины размера исходного дерева.

Итак, в случае дерева идея "разделяй и властвуй" из предыдущего пункта будет формулироваться так: [[#l1|найдем центроид]]. Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> {{---}} размер дерева. Тогда, как и в упрощенной версии задачи {{---}} рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,\dots, t_k</tex>, после чего попытаемся найти недостающие пары вершин, находящиехя находящиеся в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы: пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве <math>t_i</math> и мы в некоторой структуре данных <math>S</math> храним все вершины остальных деревьев (каждую вершину задаем парой <math>(depth(v), length(v))</math> {{---}} глубина вершины и длина пути до нее из корня поддерева), расстояние до которых от корня их поддерева не превышает <math>min(l, n)</math>. Тогда просто пройдемся по всем вершинам <math>u</math> поддерева <math>t_i</math> и прибавим к ответу число вершин в структуре <math>S</math>, таких, что <tex>depth(u) \leqslant l - depth(v)</tex> и <tex>length(u) \leqslant l - length(v)</tex>. Это двумерные запросы, на которые можно отвечать за <math>O(log^2(n)</math> с помощью [[Многомерное_дерево_отрезков|2d-дерева отрезков]], либо за <math>O(log(n))</math> с помощью [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)|техники поиска точек в d-мерном пространстве]]. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.

Оценим итоговую асимптотику: <tex>T(n) = k * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное рекуррентное соотношение, получим <math>O(n \cdot log(n))</math>.

Рассмотрим корень дерева <math>(r)</math>. Положим изначально <math>v = r</math>. Изначально <math>|subtree(v)| = n</math>. Среди всех детей <math>v</math> выберем вершину <math>u</math> с максимальным размером поддерева. Если <math>v</math> {{---}} не центроид, то положим <math>v = u</math> и продолжим выбор нового u, иначе {{---}} остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный произвольный момент времени <math>v</math> {{---}} не центроид и размер её наддерева меньше <math>\dfrac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\dfrac{n}{2}</math>, т.е. то есть <math>|subtree(u)| > \dfrac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \dfrac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\dfrac{n}{2}</math>, значит мы будем спускаться только вниз по дереву <math>t</math>, и при переходе к вершине <math>u</math> {{---}} сыну <math>v</math> размер максимального поддерева уменьшится как минимум на <math>1</math>. Значит не более чем за <math>n</math> шагов наши действия прекратятся и мы окажемся в центроиде дерева <math>t</math>, ч.т.д.

# Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\dfrac{|subtree(c)|}{2}</tex>, то при спуске в каждую следующую вершину на пути к любому листу в дереве <math>T</math> размер поддерева вершины, в которой мы сейчас находимся, уменьшается как минимум на <math>2</math>. Значит длина всего пути до листа не превосходит <math>log(n)</math>, ч.т.д.

# Третье свойство {{---}} прямое следствие первых двух, т.к. вершина принадлежит любому центроиду <math>c</math> т.и т.т., когда c {{---}} отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.

# Для доказательства последнего свойства выберем в качестве вершины <math>c</math> <math>lca(u, v)</math> в дереве центроидов <math>T</math>. Покажем, что так выбранная вершина <math>c</math> удовлетворяет заявленным свойствам. То, что <tex>u, v \in T(c)</tex> {{---}} очевидно по определению <math>lca</math>, т.к. каждый предок любой вершины в дереве центроидов содержит эту вершину. Теперь докажем, что <math>c</math> лежит на пути между парой вершин <math>u, v</math>. Т.к. <math>c = lca(u, v)</math> в <math>T</math>, то из <math>c</math> нет ребра в такого сына, который содержит одновременно <math>u</math> и <math>v</math> в своем поддереве (в дереве <math>T</math>), значит после удаления <math>c</math> дерево <math>t</math> разделится на несколько поддеревьев, таких что вершины <math>u</math> и <math>v</math> окажутся в разных компонентах связности. А значит найдется такое ребро <math>(c, x)</math>, которое принадлежало пути из <math>u</math> в <math>v</math>, но после удаления <math>c</math> удалилось. Это доказывает то, что вершина <math>c</math> лежала на пути из <math>u</math> в <math>v</math>, ч.т.д.