186
правок
Изменения
→Введение
== Введение ==
Рассмотрим 2 задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
Задача 1 :
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида : 1) дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>abs{u - v}</tex> минимально возможное.2) дан город <tex>v</tex> и сказано, что больше он не будет принимать больных3) дан город <tex>v</tex> и сказано, что теперь он может принимать больных
}}
Задача 2:
{{Задача
|definition = Есть массив <tex>a[]</tex> положительных целых чисел из <tex>n</tex> элементов и числа <tex>W>= 0</tex> и <tex>l</tex> . Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| <= l </tex> и <tex>\sum_{i=0}^{n - 1} [a[i]] <= W</tex>.
}}
Для начала решим обе задачи. Вторая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j >= \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=n/2}^{i} [a[j]]</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{n/2 + 1} [a[i]]</tex>) - для левой. Заведем два указателя (<tex>p1</tex> и <tex>p2</tex>). Изначально установим <tex>p1 = \frac{n}{2} - l + 1, p2 = \frac{n}{2}</tex>. Пока <tex>p2 > \frac{n}{2}</tex> и <tex>p2 > </tex>.
== Статическая центроидная декомпозиция ==
