Изменения

== Предпосчет ==[[Файл:sqrt'''Корневая эвристика (Sqrt-декомпозиция)''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.png|right|540px]]Пусть нам дан массив <tex>A</tex> размерности ) над идущими подряд элементами некоторого множества размера <tex>n</tex>. Cделаем следующий предпосчет:* разделим массив <tex>Aза </tex> на блоки длины <tex>len = \lfloor O(\sqrt{n} \rfloor</tex> ; * в каждом блоке заранее предпосчитаем необходимую нам операцию;* результаты предпосчёта запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \left\lceil \frac{n}{len} \right\rceil)</tex> — количество блоков.

Пример реализации предпосчета для запроса "подсчет суммы"[[Файл:<pre>for i = 0 to n - 1 B[i / lensqrt.png|358px] += A[i]</pre>

ПердпосчетПостроение, очевидно, происходит за <tex>O(n)</tex> времени.

[[Файл:sqrt(sum).png|right|520px]]Пусть мы получили получен запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{--- }} не полностью.

Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, предпосчет значения которых мы сделали посчитали заранее.

Пример реализации обработки запроса "подсчет суммы на отрезке <tex>[l, r]</tex> " :

<pretex>left = l \circ </ lenright = r / lenend = (left + 1) * len tex> {{--- 1sum = 0}} операция, для которой было сделано построение.

<code> '''T''' query('''int''' l, '''int''' r): left = l / len right = r / len end = (left + 1) * len - 1 res = neutral <font color=green> // neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font> '''if ''' left == right '''for ''' i = l to ... r sum + res = res <tex> \circ </tex> A[i] '''else''' '''for ''' i = l to ... end sum + res = res <tex> \circ </tex> A[i] '''for ''' i = left + 1 to ... right - 1 sum + res = res <tex> \circ </tex> B[i] '''for ''' i = right * len to ... r sum + res = res <tex> \circ </tex> A[i]</precode>

Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex> было выбрано равным <tex>\lfloor \sqrt{n} \rfloor</tex>, и а <tex>cnt</tex> мы выбирали было выбрано равным <tex>~ ~ \approx left\sqrtlceil \dfrac{n}{len} \right\rceil</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> времени.

[[Файл:sqrt(+delta).png|right|264px]]Для реализации Реализация данного запроса нам, в зависимости будет зависеть от того , имеет ли операция, для которой мы сделали предпосчетсделано построение, обратную операцию или нети обладает ли она свойством коммутативности.* если есть обратная операцияоба условия выполняются, то нам необходимо поменять всего два запрос на изменение элемента, так как каждый элемент входит в ровно один элемент массива можно сделать за <tex>BO(1)</tex>;времени,* если нет обратной операциихотя бы одно из условий не выполняется, то нам придется заново запрос на изменение элемента можно сделать предпосчет за <tex>O(\sqrt{n})</tex> времени. [[Файл:sqrt(+delta).png|358px]] Примеры реализации: * <tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить, * <tex>\mathtt{newValue}</tex> {{---}} новое значение для данного блока элемента. Запрос на изменение элемента для операции, у которой есть обратная операция, и записать полученный результат в выполняется свойство коммутативности: <code> '''function''' set('''int''' p, '''T''' newValue): tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) <font color=green>// inverse(A[p]) {{---}} обратный элемент массива </font> A[p] = newValue B[p / len] = tmp <tex>B\circ </tex>newValue</code> '''Замечание:''' важность наличия свойства коммутативности подчеркивает следующий контрпример. Известно, что умножение матриц не коммутативно.Возьмем блок <tex> b_0 </tex>, как показано на иллюстрации выше, со следующими значениями:

<tex>p</tex> - номер элемента из массива <tex>Aa_1 = \begin{pmatrix} 2 & 2 \\ 2 & 3 \end{pmatrix} </tex>, который необходимо заменить; <tex>delta</tex> - на сколько нужно изменить данный элемент.

Пусть необходимо изменить значение матрицы <pretex>A[p] += deltaB[p / len] += deltaa_1 </pretex>на следующее:

Тогда значения <pretex>index = len * (p / cnt)A[p] += deltafor i = index to index + len a_1^{- 1 B[p } </ len] = min(A[i]tex>, A[i + 1])<tex> tmp </tex> и новое значение <tex> a_1 </pretex>таковы :

Таким образом, запрос на изменение элемента происходит не более чем за длину блока <tex>len</tex>tmp = b \cdot a_1^{-1} = \begin{pmatrix} 8, т.е. не более чем за <tex>O(5 & 5 \\ 13 & 8 \sqrtend{npmatrix})</tex> времени.,

<tex> a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} </tex>. Тогда новое значение <tex> b_0 </tex> следующее:  <tex> b_0 = \begin{pmatrix} 54 & 59 \\ 84 & 92 \end{pmatrix} </tex>. Хотя правильный результат: <tex> b_0 = \begin{pmatrix} 51 & 60 \\ 78 & 92 \end{pmatrix} </tex>. Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется: <code> '''function''' set('''int''' p, '''T''' newValue): index = len * (p / len) A[p] = newValue B[p / len] = neutral <font color = green> // neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font> '''for''' i = index ... index + len - 1 B[p / len] = B[p / len] <tex> \circ </tex> A[i]</code> ==См. также==* [[Дерево отрезков. Построение]]* [[Многомерное дерево отрезков]] ==Источникиинформации==* [http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]