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