Изменения
Нет описания правки
Задача <math>1</math>
{{Задача
|definition = Есть массив <tex>a</tex> положительных целых чисел из <tex>n</tex> элементов и числа . Также дано число <tex>W \geqslant 0</tex> и число <tex>рll</tex>. Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| \leqslant l </tex> и <tex>\sum_{i=0}^{n - 1} a_i \leqslant W</tex>.
}}
Задача <math>2</math>:
'''Центроидом дерева''' (англ. ''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 \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так: найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <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>.
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией divide & conquer {{---}} деревом отрезков. В предыдущем пункте мы определили статический оналог аналог divide & conquer для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition=
