Корневая декомпозиция с операциями: get, insert, erase
Корневая декомпозиция — это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера
за . Так же есть поддержка операций удаления и вставки в произвольное место
Содержание
[убрать]Идея
Пусть дан массив
размерности и запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.Будем поддерживать разбиение массива
на блоки. Введем операцию , которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на . Введем вспомогательную функцию . Данная функция позволяет вновь перестроить структуру.Реализуем две основные операции
и . Остальные операции выразим через них. Пусть время работы операции и операции , где - длина блоков, - количество блоков.Выберем
, тогда после операции будет блоков, где текущие количество элементов в структуре. Заметим, что любая операция добавляет не более, чем новых блоков. После каждых операций вызовем .Асимптотика:
.Найдем минимум функции, который достигается при
.Итоговое время работы:
.Построение
Пусть дан массив
размерности . Cделаем следующие действия:- разделим массив на блоки длины
- в каждом блоке заранее посчитаем необходимую операцию
- для каждого блока сохраним индекс самого левого и самого правого элемента в массивах
- результаты подсчета запишем в массив размерности , где — количество блоков
- заведем массив , в котором храним актуальный порядок блоков. соответствует порядку
Пример реализации построения для операции
:
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]
Построение, происходит за
времени.Операций split
Данная операций нужна для реализации операций:
, , . Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс называется разрезом, если не существует такого актуального блока, которому принадлежит индекс и одновременно.Пусть получен запрос на выполнение операции для индекса
. Этот индекс входит ровно в один блок массива , пусть индекс этого блока – . После операции этот блок поделится на и , если был в середине блока, иначе уже является разрезом и никакая операций не требуется. Как мы видим после операции у нас появилось максимум два новых блока.Для удобства реализации в массивы
можно только дописывать новую информацию в конце, что соответствует созданию новых блоков.Блок считается актуальным, если он присутствует в массиве
.
Перейдем к реализации:
- Найдем в какой актуальный блок входит
- Проверим, что не является разрезом
- Создадим два новых блока. Для каждого из них посчитаем значение функции, а также зададим правильные значения в массивах и
- Удалим старый блок из перестановки и запишем туда два других.
int createNewBlock(int l, int r): // Вспомогательная функция. Позволяет создать блок с
по .
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. Время работы
T.insert(ind. first) // операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы
T.insert(ind + 1, second)
return ind
Асимптотика:
– поиск нужного блока, – подсчет функции. Итог: Так же заметим, что мы увеличили на .Операций rebuild
Вторая необходимая операция – это
. Заметим, что после операций количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб не стало слишком большим будем полностью перестраивать структуру изменяя на базовое значение равное .Будем восстанавливать из актуальных блоков массив
. Потом очищать все текущие блоки, а затем вызывать операцию для построение новой структуры.
Перейдем к реализации:
- Восстановим актуальную версию массива
- Очистим массивы , удалив все текущие блоки
- Вызовем операцию
void rebuild():
tempA // временная актуальная копия массива
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()
Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре.
Операций get
Пусть получен запрос на выполнение операции на отрезке
. Будем выполнять операции только на целых блоках, изменим нашу структуры так, чтобы граница отрезка никогда не попадал в середину блока.
Перейдем к реализации:
- Разделим наши блоки при помощи операции
- Посчитаем операцию на целых блоках использую массив
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
Асимптотика:
и . Итого:Операция erase
Пусть получен запрос на выполнение операции удаления числа на позиции
. Аналогично операции , мы не хотим удалять из середины блока. Когда является единственным числом в блоке, мы можем просто удалить его из массива .
Перейдем к реализации:
- Разделим наши блоки при помощи операции
- Посчитаем операцию на целых блоках использую массив
void erase(int x):
split(x - 1)
ind = split(x)
T.erase(ind)
Асимптотика:
Операция insert
Пусть получен запрос на выполнение вставить число
после числа с индексом . Аналогично операции , мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число в конец массива и создать новый блок размер , который ссылается на это число.Перейдем к реализации:
- Разделим наши блоки при помощи операции
- Добавим в конец число
- Создадим новый блок и вставим в нужное место
void insert(int x, int y):
ind = split(x)
A.push_back(y)
indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
T.insert(ind, indexNewBlock)
Асимптотика: