Редактирование: Статистики на отрезках. Корневая эвристика


'''Корневая эвристика (Sqrt-декомпозиция)''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера <tex>n</tex> за <tex> O(\sqrt n)</tex>.

== Построение ==
Пусть дан массив <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 \dfrac{n}{len} \right\rceil</tex> {{---}} количество блоков.

[[Файл:sqrt.png|358px]]

Пример реализации построения массива <tex>B</tex> для операции <tex> \circ </tex>:
<code>
 '''void''' build():
     '''for''' i = 0 ... cnt
         B[i] = neutral                <font color=green>// neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
     '''for''' i = 0 ... n - 1
         B[i / len] = B[i / len] <tex> \circ </tex> A[i]
</code>


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

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

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

[[Файл:sqrt(sum).png|358px]]

Пример реализации обработки запроса:

<tex> \circ </tex> {{---}} операция, для которой было сделано построение.

<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 ... r
             res = res <tex> \circ </tex> A[i]
     '''else'''
         '''for''' i = l ... end
             res = res <tex> \circ </tex> A[i]
         '''for''' i = left + 1 ... right - 1
             res = res <tex> \circ </tex> B[i]
         '''for''' i = right * len ... r
             res = res <tex> \circ </tex> A[i]
</code>


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

== Запрос на изменение элемента ==
Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.
* если оба условия выполняются, то запрос на изменение элемента можно сделать за <tex>O(1)</tex> времени,
* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.

[[Файл:sqrt(+delta).png|358px]]

Примеры реализации:

<tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>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> \circ </tex> newValue
</code>

'''Замечание:''' важность наличия свойства коммутативности подчеркивает следующий контрпример. Известно, что умножение матриц не коммутативно. Возьмем блок <tex> b_0 </tex>, как показано на иллюстрации выше, со следующими значениями: 

<tex> b_0 = \begin{pmatrix} 27 & 32 \\ 42 & 50 \end{pmatrix} </tex> , 

<tex> a_0 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} </tex> , 

<tex> a_1 = \begin{pmatrix} 2 & 2 \\ 2 & 3 \end{pmatrix} </tex> , 

<tex> a_2 = \begin{pmatrix} 3 & 3 \\ 3 & 4 \end{pmatrix} </tex>.

Пусть необходимо изменить значение матрицы <tex> a_1 </tex> на следующее: 

<tex> \mathtt{newValue} = a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} </tex>.

Тогда значения <tex> a_1^{-1} </tex>, <tex> tmp  </tex> и новое значение <tex> a_1 </tex> таковы :
 

<tex> a_1^{-1} = \begin{pmatrix} 1,5 & -1 \\ -1 & 1 \end{pmatrix} </tex>,

<tex> tmp = b \cdot a_1^{-1} = \begin{pmatrix} 8,5 & 5 \\ 13 & 8 \end{pmatrix} </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-декомпозиция]
* [http://habrahabr.ru/post/138946/#habracut Sqrt-декомпозиция (корневая оптимизация)]


[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]