Статистики на отрезках. Корневая эвристика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание)
м (rollbackEdits.php mass rollback)
 
(не показано 106 промежуточных версий 10 участников)
Строка 1: Строка 1:
== Определение ==
 
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>.
 
  
== Описание ==
+
'''Корневая эвристика (Sqrt-декомпозиция)''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера <tex>n</tex> за <tex> O(\sqrt n)</tex>.
''Привидем описание для операции суммирования''
 
  
Дан массив <tex>A[0 \ldots n-1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>\sqrt{n}</tex> (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока <tex>(len \approx \sqrt{n})</tex>, а <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</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> {{---}} количество блоков.
  
[[Файл:Корневая эвристика.png]]
+
[[Файл:sqrt.png|358px]]
  
Через <tex>b_k</tex> мы обозначили результат предпосчёта в k-ом подотрезке.
+
Пример реализации построения массива <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>[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>\sum_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i</tex>
 
  
Теперь разрешим изменять элементы. Если меняется какой-то элемент <tex>a_i</tex>, то достаточно обновить значение <tex>b_k</tex> в том блоке, в котором этот элемент находится:
+
Построение, очевидно, происходит за <tex>O(n)</tex> времени.
  
<tex>b_k\ += a_i - old\_a_i\_val</tex>
+
== Обработка запроса ==
 +
Пусть получен запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{---}} не полностью.
  
<tex>(k = i / len)</tex>
+
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
  
==Оценка сложности==
+
[[Файл:sqrt(sum).png|358px]]
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>\approx \sqrt{n}</tex>, то всего для вычисления суммы в отрезке <tex>[l \ldots r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> операций.
 
  
==Источники==
+
Пример реализации обработки запроса:
[http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]
+
 
 +
<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>\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-декомпозиция (корневая оптимизация)]
 +
 
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Дерево отрезков]]

Текущая версия на 19:30, 4 сентября 2022

Корневая эвристика (Sqrt-декомпозиция) — это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера [math]n[/math] за [math] O(\sqrt n)[/math].

Построение

Пусть дан массив [math]A[/math] размерности [math]n[/math]. Cделаем следующие действия:

  • разделим массив [math]A[/math] на блоки длины [math]len = \lfloor \sqrt{n} \rfloor[/math] ,
  • в каждом блоке заранее посчитаем необходимую операцию,
  • результаты подсчета запишем в массив [math]B[/math] размерности [math]cnt[/math], где [math]cnt = \left\lceil \dfrac{n}{len} \right\rceil[/math] — количество блоков.

Sqrt.png

Пример реализации построения массива [math]B[/math] для операции [math] \circ [/math]:

void build():
    for i = 0 ... cnt
        B[i] = neutral                // neutral — нейтральный элемент для операции [math] \circ [/math] 
    for i = 0 ... n - 1
        B[i / len] = B[i / len] [math] \circ [/math] A[i]


Построение, очевидно, происходит за [math]O(n)[/math] времени.

Обработка запроса

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

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

Sqrt(sum).png

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

[math] \circ [/math] — операция, для которой было сделано построение.

T query(int l, int r):
    left = l / len
    right = r / len
    end = (left + 1) * len - 1
    res = neutral                       // neutral — нейтральный элемент для операции [math] \circ [/math] 
    if left == right
        for i = l ... r
            res = res [math] \circ [/math] A[i]
    else
        for i = l ... end
            res = res [math] \circ [/math] A[i]
        for i = left + 1 ... right - 1
            res = res [math] \circ [/math] B[i]
        for i = right * len ... r
            res = res [math] \circ [/math] A[i]


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

Запрос на изменение элемента

Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.

  • если оба условия выполняются, то запрос на изменение элемента можно сделать за [math]O(1)[/math] времени,
  • если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за [math]O(\sqrt{n})[/math] времени.

Sqrt(+delta).png

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

  • [math]p[/math] — номер элемента из массива [math]A[/math], который необходимо заменить,
  • [math]\mathtt{newValue}[/math] — новое значение для данного элемента.

Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:

function set(int p, T newValue):
    tmp = B[p / len] [math] \circ [/math] inverse(A[p])   // inverse(A[p]) — обратный элемент
    A[p] = newValue
    B[p / len] = tmp [math] \circ [/math] newValue

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

[math] b_0 = \begin{pmatrix} 27 & 32 \\ 42 & 50 \end{pmatrix} [/math] ,

[math] a_0 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} [/math] ,

[math] a_1 = \begin{pmatrix} 2 & 2 \\ 2 & 3 \end{pmatrix} [/math] ,

[math] a_2 = \begin{pmatrix} 3 & 3 \\ 3 & 4 \end{pmatrix} [/math].

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

[math] \mathtt{newValue} = a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} [/math].

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


[math] a_1^{-1} = \begin{pmatrix} 1,5 & -1 \\ -1 & 1 \end{pmatrix} [/math],

[math] tmp = b \cdot a_1^{-1} = \begin{pmatrix} 8,5 & 5 \\ 13 & 8 \end{pmatrix} [/math] ,

[math] a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} [/math].

Тогда новое значение [math] b_0 [/math] следующее:


[math] b_0 = \begin{pmatrix} 54 & 59 \\ 84 & 92 \end{pmatrix} [/math].

Хотя правильный результат: [math] b_0 = \begin{pmatrix} 51 & 60 \\ 78 & 92 \end{pmatrix} [/math].

Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется:

function set(int p, T newValue):
    index = len * (p / len)
    A[p] = newValue
    B[p / len] = neutral              // neutral — нейтральный элемент для операции [math] \circ [/math] 
    for i = index ... index + len - 1
        B[p / len] = B[p / len] [math] \circ [/math] A[i]

См. также

Источники информации