47
правок
Изменения
м
res = res <tex> \circ </tex> A[i]
Тире заменено шаблоном, псевдокод отформатирован
'''Корневая эвристика (Sqrt-декомпозиция)''' — {{---}} это метод, или структура данных, которая позволяет выполнять ассоциативные операции над отрезками (например, суммирование элементов, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>.
== Построение ==
* разделим массив <tex>A</tex> на блоки длины <tex>len = \lfloor \sqrt{n} \rfloor</tex> ;
* в каждом блоке заранее посчитаем необходимую нам операцию;
* результаты подсчета запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — {{---}} количество блоков.
[[Файл:sqrt.png|358px]]
== Обработка запроса ==
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{- --}} не полностью.
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
if left == right
for i = l to r
else
for i = l to end
Примеры реализации:
<tex>p</tex> {{- --}} номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>newValue</tex> {{--- }} новое значение для данного элемента.
<tex> \circ </tex> {{- --}} операция, для которой было сделано построение.
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
