338
правок
Изменения
Нет описания правки
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>. }}
[[Файл:sqrt.png|right|540px]]
Пусть нам дан массив <tex>A</tex> размерности <tex>n</tex>. Cделаем следующий предпосчет:
</pre>
[[Файл:sqrt(sum).png|right|520px]]
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
sum += A[i]
</pre>
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>~ ~ \approx \sqrt{n}</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> времени.
== Запрос на изменение элемента ==
[[Файл:sqrt(+delta).png|right|264px]]
<tex>p</tex> - номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>delta</tex> - на сколько нужно изменить данный элемент.
Запрос на изменение элемента для суммы (есть обратная операция):
<pre>
A[p] += delta
</pre>
==Источники==
