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

Корневая эвристика (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] — количество блоков.

Пример реализации построения массива [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] необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.

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

[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] времени.

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

• [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]

См. также

• Дерево отрезков. Построение
• Многомерное дерево отрезков

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

• Maximal:: algo:: Sqrt-декомпозиция
• Sqrt-декомпозиция (корневая оптимизация)