Изменения

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

== Построение ==Пусть дан массив <tex> A</tex> размерности <tex>n</tex>. Cделаем следующие действия:* разделим массив <tex>A</tex> на блоки длины <tex>len = \underbracelfloor \sqrt{a_0n} \rfloor</tex> , a_1* в каждом блоке заранее посчитаем необходимую операцию,* результаты подсчета запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \ldots a_{len - 1}}_{b_0}, left\ldots lceil \underbracedfrac{a_{lenn}, \ldots a_{2 len - 1}}_{b_1} , \ldots right\underbracerceil</tex> {a_{(cnt - 1) len} \ldots a_{n-1}}_{b_{cnt - 1}} </tex>количество блоков.

Приведем описание для операции минимума[[Файл:=== Запрос ===sqrt.png|358px]]

Пусть мы получили запрос на извлечение минимума на отрезке Пример реализации построения массива <tex> [l \ldots r] B</tex>. Отрезок может охватить некоторые блоки для операции <tex> b \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>[l \ldots r]</tex>Построение, надо найти минимум среди элементов в "неполных блоках": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>очевидно, и минимума среди происходит за <tex>b_i</tex> во всех блоках, начиная с k и заканчивая p:<tex>\min_{i = l}^r a_i = \minO(\min_{i = l}^{(k + 1)len - 1}(a_i),\min_{i = k}^p( b_i),\min_{i = p + 1}^r (a_i)n)</tex>времени.

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

Таким образом, для того чтобы найти результат операции на отрезке <tex>b_k\ = \min(new\_value[l, a_j)r]</tex>необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, где <tex>a_j</tex> - элементы блока <tex>b_k</tex>значения которых мы посчитали заранее.

<tex>[[Файл:sqrt(k = i / lensum)</tex>.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>\approx left\lceil \sqrtdfrac{n}{len} \right\rceil</tex>, то всего для вычисления минимума и пересчитывания выполнения операции на отрезке <tex>[l \ldots , 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>\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> \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-декомпозиция (корневая оптимизация)]