Корневая декомпозиция с операциями: get, insert, erase

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

Идея

Пусть дан массив [math]A[/math] размерности [math]n[/math] и [math]m[/math] запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.

Будем поддерживать разбиение массива [math]A[/math] на блоки. Введем операцию [math]split[/math], которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на [math]O(1)[/math]. Введем вспомогательную функцию [math]rebuild[/math]. Данная функция позволяет вновь перестроить структуру.

Реализуем две основные операции [math]split[/math] и [math]rebuild[/math]. Остальные операции выразим через них. Пусть время работы операции [math]split[/math] [math]O(cnt + len)[/math] и операции [math]rebuild[/math] [math]O(|A| + cnt)[/math], где [math]len[/math] - длина блоков, [math]cnt[/math] - количество блоков.

Выберем [math]len = \sqrt n[/math], тогда после операции [math]build[/math] будет [math]cnt = O(\sqrt n)[/math] блоков, где [math]n[/math] текущие количество элементов в структуре. Заметим, что любая операция добавляет не более, чем [math]4[/math] новых блоков. После каждых [math]k[/math] операций вызовем [math]rebuild[/math].

Асимптотика: [math]O((m / k) \cdot (n + 4 \cdot k) + m \cdot (len + 4 \cdot k))[/math].

Найдем минимум функции, который достигается при [math]k = O(\sqrt n)[/math].

Итоговое время работы: [math]O(\sqrt n \cdot (n + m))[/math].

Построение

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

• разделим массив [math]A[/math] на блоки длины [math]len = \lfloor \sqrt{n} \rfloor[/math]
• в каждом блоке заранее посчитаем необходимую операцию
• для каждого блока сохраним индекс самого левого и самого правого элемента в массивах [math]L, R[/math]
• результаты подсчета запишем в массив [math]B[/math] размерности [math]cnt[/math], где [math]cnt = \left\lceil \dfrac{n}{len} \right\rceil[/math] — количество блоков
• заведем массив [math]T[/math], в котором храним актуальный порядок блоков. [math]T = [0, 1, ... cnt - 1][/math] соответствует порядку [math]B_0, B_1 , … , B_{cnt-1}[/math]

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

void build():
    for i = 0 ... n - 1
        T[i] = i
        L[i] = i * len
        R[i] = (i + 1) * len - 1
    for i = 0 ... n - 1
        B[i / len] = B[i / len] + A[i]

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

Операций split

Данная операций нужна для реализации операций: [math]insert[/math], [math]erase[/math], [math]get[/math]. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс [math]i[/math] называется разрезом, если не существует такого актуального блока, которому принадлежит индекс [math]i[/math] и [math]i + 1[/math] одновременно.

Пусть получен запрос на выполнение операции для индекса [math]x[/math]. Этот индекс входит ровно в один блок массива [math]B[/math], пусть индекс этого блока – [math]ind[/math]. После операции [math]split[/math] этот блок поделится на [math][L[ind], x][/math] и [math][x + 1, R[ind]][/math], если [math]x[/math] был в середине блока, иначе [math]x[/math] уже является разрезом и никакая операций не требуется. Как мы видим после операции у нас появилось максимум два новых блока.

Для удобства реализации в массивы [math]B, L, R[/math] можно только дописывать новую информацию в конце, что соответствует созданию новых блоков.

Блок считается актуальным, если он присутствует в массиве [math]T[/math].

Перейдем к реализации:

• Найдем в какой актуальный блок входит [math]x[/math]
• Проверим, что [math]x[/math] не является разрезом
• Создадим два новых блока. Для каждого из них посчитаем значение функции, а также зададим правильные значения в массивах [math]L[/math] и [math]R[/math]
• Удалим старый блок из перестановки и запишем туда два других.

int createNewBlock(int l, int r): // Вспомогательная функция. Позволяет создать блок с [math]l[/math] по [math]r[/math].
    result = 0
    for i = l ... r
        result = result + A[i]
    B.push_back(result)
    L.push_back(l)
    R.push_back(r) 
    cnt++
    return cnt - 1

int split(int x):
    ind = 0
    for i = 0 ... |T| - 1
           if L[i] <= x and x <= R[i]
                    ind = i
    if L[ind] == x or R[ind] == x or x < 0
           return 0
    first = createNewBolock(L[ind], x)
    second = createNewBolock(x, R[ind])
    T.erase(ind) // операций T.erase(x) удаляет элемент под номером x и сдвигает массив T. Время работы [math]O(|T|)[/math]
    T.insert(ind. first) // операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы [math]O(|T|)[/math]
    T.insert(ind + 1, second)
    return ind

Асимптотика: [math]O(cnt)[/math] – поиск нужного блока, [math]O(len)[/math] – подсчет функции. Итог: [math]O(len + cnt)[/math] Так же заметим, что мы увеличили [math]cnt[/math] на [math]2[/math].

Операций rebuild

Вторая необходимая операция – это [math]rebuild[/math]. Заметим, что после операций [math]split[/math] количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб [math]cnt[/math] не стало слишком большим будем полностью перестраивать структуру изменяя [math]cnt[/math] на базовое значение равное [math]cnt = \left\lceil \dfrac{n}{len} \right\rceil[/math].

Будем восстанавливать из актуальных блоков массив [math]A[/math]. Потом очищать все текущие блоки, а затем вызывать операцию [math]build[/math] для построение новой структуры.

Перейдем к реализации:

• Восстановим актуальную версию массива [math]A[/math]
• Очистим массивы [math]B, L, R[/math], удалив все текущие блоки
• Вызовем операцию [math]build[/math]

void rebuild():
    tempA // временная актуальная копия массива [math]A[/math]
    for i = 0 ... |T| - 1
           for j = L[i] ... R[i]
                   tempA.push_back(A[j])
    A = tempA
    B.clear()
    L.clear()
    R.clear()
    build()

Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. [math]O(|A| + cnt)[/math]

Операций get

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

Перейдем к реализации:

• Разделим наши блоки при помощи операции [math]split[/math]
• Посчитаем операцию на целых блоках использую массив [math]B[/math]

int get(int l, int r):
    result = 0
    indexL = split(l – 1)
    indexR = split(r) – 1 
    for i = indexL ... indexR
         result = result + B[T[i]]
    return result

Асимптотика: [math]O(split)[/math] и [math]O(|T|)[/math]. Итого: [math]O(cnt + len)[/math]

Операция erase

Пусть получен запрос на выполнение операции удаления числа на позиции [math]x[/math]. Аналогично операции [math]get[/math], мы не хотим удалять из середины блока. Когда [math]x[/math] является единственным числом в блоке, мы можем просто удалить его из массива [math]T[/math].

Перейдем к реализации:

• Разделим наши блоки при помощи операции [math]split[/math]
• Посчитаем операцию на целых блоках использую массив [math]B[/math]

void erase(int x):
    split(x - 1) 
    ind = split(x)
    T.erase(ind)

Асимптотика: [math]O(cnt + len)[/math]

Операция insert

Пусть получен запрос на выполнение вставить число [math]y[/math] после числа с индексом [math]x[/math]. Аналогично операции [math]get[/math], мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число [math]x[/math] в конец массива [math]A[/math] и создать новый блок размер [math]1[/math], который ссылается на это число.

Перейдем к реализации:

• Разделим наши блоки при помощи операции [math]split[/math]
• Добавим в конец [math]A[/math] число [math]y[/math]
• Создадим новый блок и вставим в нужное место

void insert(int x, int y):
    ind = split(x)
    A.push_back(y)
    indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
    T.insert(ind, indexNewBlock)

Асимптотика: [math]O(cnt + len)[/math]

См. также

• Дерево отрезков. Построение
• Многомерное дерево отрезков
• Статистики на отрезках. Корневая эвристика