338
правок
Изменения
Нет описания правки
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>. }}
== Предпосчет Построение ==
[[Файл:sqrt.png|right|540px]]
Пусть нам дан массив <tex>A</tex> размерности <tex>n</tex>. Cделаем следующий предпосчетследующие действия:
* разделим массив <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> — количество блоков.
Пример реализации предпосчета построения массива <tex>B</tex> для операции <tex> \circ </tex>:
<code>
for i = 0 to n - 1
</code>
== Обработка запроса ==
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, предпосчет значения которых мы сделали посчитали заранее.
Пример реализации обработки запроса:
<tex> \circ </tex> - операция, для которой был сделан предпосчетбыло сделано построение.
<code>
right = r / len
end = (left + 1) * len - 1
res = a[l]??? // где ??? - нейтральный элемент для операции <tex> \circ </tex>
if left == right
for i = l + 1 to r
res = res <tex> \circ </tex> A[i]
else
for i = l + 1 to end
res = res <tex> \circ </tex> A[i]
for i = left + 1 to right - 1
== Запрос на изменение элемента ==
[[Файл:sqrt(+delta).png|right|264px]]
Реализации данного запроса будет зависеть от того, имеет ли операция, для которой мы сделали предпосчетпостроение, обратную операцию и обладает ли она свойством коммутативности.* если обратная операция существует, и выполняется свойство коммутативностиоба условия выполняются, то нам не придется заново пересчитывать значение для блоказапрос на изменение элемента мы можем сделать за <tex>O(1)</tex> времени;* если хотя бы одно из условий не выполняется, то нам придется заново пересчитать значение для блока, к которому принадлежит элемент указанный в запросе, и записать полученный результат в соответствующий элемент массива запрос на изменение элемента можно сделать за <tex>BO(\sqrt{n})</tex>времени.
<tex>p</tex> - номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>newValue</tex> - новое значение для данного элемента.
<tex> \circ </tex> - операция, для которой был сделан предпосчетбыло сделано построение.
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
<code>
tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) // inverse(A[p]) - обратный элемент
A[p] = newValue
<code>
index = len * (p / len)
A[p] = newValue
B[p / len] = A[index]??? // где ??? - нейтральный элемент для операции <tex> \circ </tex> for i = index + 1 to index + len - 1
B[p / len] = B[p / len] <tex> \circ </tex> A[i]
</code>
==Источники==
