Изменения

Будем поддерживать разбиение массива <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>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>.

Данная операций нужна для реализации операций: reverse, <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> можно только дописывать новую информацию в конце, что соответствует созданию новых блоков.

'''int''' createNewBlock('''int''' l, '''int''' r):// Вспомогательная функция. Позволяет создать блок с <math>l</math> по <math>r</math>.

Вторая необходимая операция – это <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>build</math>

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

* Разделим наши блоки при помощи операции <math>split</math>

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

* Разделим наши блоки при помощи операции <math>split</math>

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

* Разделим наши блоки при помощи операции <math>split</math>