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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Корневая декомпозиция ''' {{---}} это подход к реализации ассоциативных операций (например...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Корневая декомпозиция ''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера <tex>n</tex> за <tex> O(\sqrt n)</tex>. Так же есть поддержка операций удаления и вставки в произвольное место
+
'''Корневая декомпозиция ''' с операциями удаления, вставки в произвольное место и вычисления функции на отрезке.
  
  
== Идея ==
+
== Описание модификации исходной структуры ==
 
Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.
 
Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.
  
Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию split, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Так же будет другая вспомогательная функция rebuild. Данная функция позволяет вновь перестроить структуру.
+
Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию <math>\mathrm{split}</math>, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Введем вспомогательную функцию <math>\mathrm{rebuild}</math>. Данная функция позволяет вновь перестроить структуру.
  
Реализуем две основные операции split и rebuild. Остальные операции выразим через них.
+
Реализуем две основные операции <math>\mathrm{split}</math> и <math>\mathrm{rebuild}</math>. Остальные операции выразим через них.
Пусть время работы операции split: <math>O(cnt + len)</math> и операции rebuild: <math>O(|A| + cnt)</math>.
+
Пусть время работы операции составляет <math>\mathrm{split}</math> <math>O(cnt + len)</math> и операции <math>\mathrm{rebuild}</math> составляет <math>O(|A| + cnt)</math>, где <math>len</math> {{---}} длина блоков, <math>cnt</math> {{---}} количество блоков. Ниже будет приведена реализация этих функций с такой асимптотикой
  
Выберем <math>len = \sqrt n</math>, тогда после операции build будет <math>cnt = O(\sqrt n)</math> блоков, где <math>n</math> текущие количество элементов в структуре. Заметим, что любая операция добавляет не более, чем <math>4</math> новых блоков. После каждых <math>k</math> операций вызовем rebuild.  
+
Выберем <math>len = \sqrt n</math>, тогда после операции <math>build</math> будет <math>cnt = O(\sqrt n)</math> блоков, где <math>n</math> текущие количество элементов в структуре. Заметим, что любая операция добавляет не более, чем <math>4</math> новых блоков. После каждых <math>k</math> операций вызовем <math>\mathrm{rebuild}</math>.  
  
Асимптотика: <math>O((m / k) \cdot (n + 4 \cdot k) + m \cdot (len + 4 \cdot k))</math>.  
+
Асимптотика выполнения <math>m</math> запросов составляет: <math>O\left(\dfrac m k \cdot (n + 4 \cdot k) + m \cdot (len + 4 \cdot k)\right)</math>.
  
 
Найдем минимум функции, который достигается при <math>k = O(\sqrt n)</math>.  
 
Найдем минимум функции, который достигается при <math>k = O(\sqrt n)</math>.  
  
 
Итоговое время работы: <math>O(\sqrt n \cdot (n + m))</math>.
 
Итоговое время работы: <math>O(\sqrt n \cdot (n + m))</math>.
 +
 +
  
 
== Построение ==
 
== Построение ==
Пусть дан массив <math>A</math> размерности <math>n</math>. Cделаем следующие действия:
+
<noinclude>
* разделим массив <math>A</math> на блоки длины <math>len = \lfloor \sqrt{n} \rfloor</math> ,  
+
{{Задача
 +
|definition = Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: добавить элемент <math>y</math> после элемента <math>x</math>, удалить элемент с индексом <math>x</math>, посчитать сумму на отрезке <math>[l, r]</math>.
 +
}}
 +
</noinclude>
 +
 
 +
Cделаем следующие действия:
 +
* разделим массив <math>A</math> на блоки длины <math>len = \lfloor \sqrt{n} \rfloor</math>,
 
* в каждом блоке заранее посчитаем необходимую операцию,
 
* в каждом блоке заранее посчитаем необходимую операцию,
 
* для каждого блока сохраним индекс самого левого и самого правого элемента в массивах <math>L, R</math>,
 
* для каждого блока сохраним индекс самого левого и самого правого элемента в массивах <math>L, R</math>,
 
* результаты подсчета запишем в массив <math>B</math> размерности <math>cnt</math>, где <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</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>T</math>, в котором храним актуальный порядок блоков. <math>T = [0, 1, \ldots, cnt - 1]</math> соответствует порядку <math>B_0, B_1 , \ldots , B_{cnt-1}</math>.
  
 
Пример реализации построения для операции <math> + </math>:
 
Пример реализации построения для операции <math> + </math>:
Строка 30: Строка 38:
 
<code>
 
<code>
 
  '''void''' build():
 
  '''void''' build():
    '''for''' i = 0 ... n - 1
+
    '''for''' i = 0 ... n - 1
        T[i] = i
+
        T[i] = i
        L[i] = i * len
+
        L[i] = i * len
        R[i] = (i + 1) * len - 1
+
        R[i] = (i + 1) * len - 1
    '''for''' i = 0 ... n - 1
+
    '''for''' i = 0 ... n - 1
        B[i / len] = B[i / len] + A[i]
+
        B[i / len] = B[i / len] + A[i]
 
</code>
 
</code>
  
Построение, происходит за <tex>O(n)</tex> времени.
+
Построение происходит за <tex>O(n)</tex> времени.
 +
 
 +
== Операция split==
 +
Данная операций нужна для реализации операций: <math>\mathrm{insert}</math>, <math>\mathrm{erase}</math>, <math>\mathrm{get}</math>. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс <math>i</math> называется разрезом, если не существует такого актуального блока, которому принадлежит индекс <math>i</math> и <math>i + 1</math> одновременно.
  
== Операций split ==
+
Пусть получен запрос на выполнение операции для индекса <math>x</math>. Этот индекс входит ровно в один блок массива <math>B</math>, пусть индекс этого блока
Данная операций нужна для реализации операций: reverse, insert, erase. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс <math>i</math> называется разрезом, если не существует такого актуального блока, которому принадлежит индекс <math>i</math> и <math>i + 1</math> одновременно.
+
{{---}} <math>ind</math>. После операции <math>\mathrm{split}</math> этот блок поделится на <math>[L[ind], x]</math> и <math>[x + 1, R[ind]]</math>, если <math>x</math> был в середине блока, иначе <math>x</math> уже является разрезом и никакая операций не требуется. Как мы видим после операции у нас появилось максимум два новых блока.
  
Пусть получен запрос на выполнение операции для индекса <math>x</math>. Этот индекс входит ровно в один блок массива <math>B</math>, пусть индекс этого блока – <math>ind</math>. После операции split этот блок поделится на <math>[L[ind], x]</math> и <math>[x + 1, R[ind]]</math>, если <math>x</math> был в середине блока, иначе <math>x</math> уже является разрезом и никакая операций не требуется. Как мы видим после операции у нас появилось максимум два новых блока.
+
Для удобства реализации в массивы <math>B, L, R</math> можно только дописывать новую информацию в конце, что соответствует созданию новых блоков.
  
Для удобства реализации в массивы <math>B, L, R</math> мы можем только дописывать новую информацию в конце, что соответствует созданию новых блоков.
 
 
Блок считается актуальным, если он присутствует в массиве <math>T</math>.
 
Блок считается актуальным, если он присутствует в массиве <math>T</math>.
  
Строка 56: Строка 66:
  
 
<code>
 
<code>
  '''int''' createNewBlock('''int''' l, '''int''' r):
+
  '''int''' createNewBlock('''int''' l, '''int''' r): <font color=green>// Вспомогательная функция. Позволяет создать блок с <math>l</math> по <math>r</math>.</font>
    result = 0
+
    result = 0
    '''for''' i = l ... r
+
    '''for''' i = l ... r
        result = result + A[i]
+
        result = result + A[i]
    B.push_back(result)
+
    B.pushBack(result)
    L.push_back(l)
+
    L.pushBack(l)
    R.push_back(r)  
+
    R.pushBack(r)  
    cnt++
+
    cnt++
    return cnt - 1
+
    '''return''' cnt - 1
 
</code>
 
</code>
  
 
<code>
 
<code>
 
  '''int''' split('''int''' x):
 
  '''int''' split('''int''' x):
    ind = 0
+
    ind = 0
    '''for''' i = 0 ... |T| - 1
+
    '''for''' i = 0 ... |T| - 1
            if L[i] <= x and x <= R[i]
+
        '''if''' L[i] <= x '''and''' x <= R[i]
                    ind = i
+
            ind = i
    if L[ind] == x or R[ind] == x or x < 0
+
    '''if''' L[ind] == x '''or''' R[ind] == x '''or''' x < 0
            return 0
+
        '''return''' 0
    first = createNewBolock(L[ind], x)
+
    first = createNewBlock(L[ind], x)
    second = createNewBolock(x, R[ind])
+
    second = createNewBlock(x, R[ind])
    T.erase(ind) // операций T.erase(x) удаляет элемент под номером x и сдвигает массив T. Время работы <math>O(|T|)</math>
+
    T.erase(ind) <font color=green>// операций T.erase(x) удаляет элемент под номером x и сдвигает массив T. Время работы <tex>O(|T|)</tex> </font>
    T.insert(ind. first) // операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы <math>O(|T|)</math>
+
    T.insert(ind. first) <font color=green>// операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы <tex>O(|T|)</tex> </font>
    T.insert(ind + 1, second)
+
    T.insert(ind + 1, second)
    return ind
+
    '''return''' ind
 
</code>
 
</code>
  
Асимптотика: <math>O(cnt)</math> – поиск нужного блока, <math>O(len)</math> – подсчет функции. Итог: <math>O(len + cnt)</math>
+
Асимптотика: <math>O(cnt)</math> – поиск нужного блока, <math>O(len)</math> – подсчет функции. Итог: <math>O(len + cnt)</math>.
Так же заметим, что мы увеличили <math>cnt</math> на <math>2</math>.
+
Также заметим, что мы увеличили <math>cnt</math> на <math>2</math>.
  
== Операций rebuild ==
+
== Операция rebuild==
Вторая необходимая операция – это rebuild. Заметим, что после операций split количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб <math>cnt</math> не стало слишком большим будем полностью перестраивать структуру изменяя <math>cnt</math> на базовое значение равное <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</math>.  
+
Вторая необходимая операция {{---}} <math>\mathrm{rebuild}</math>. Заметим, что после операций <math>\mathrm{split}</math> количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб <math>cnt</math> не стало слишком большим будем полностью перестраивать структуру изменяя <math>cnt</math> на базовое значение равное <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</math>.  
  
Будем восстанавливать из актуальных блоков массив <math>A</math>. Потом очищать все текущие блоки, а затем вызывать операцию build для построение новой структуры.
+
Будем восстанавливать из актуальных блоков массив <math>A</math>. Потом очищать все текущие блоки, а затем вызывать операцию <math>\mathrm{build}</math> для построение новой структуры.
  
  
Строка 95: Строка 105:
 
* Восстановим актуальную версию массива <math>A</math>
 
* Восстановим актуальную версию массива <math>A</math>
 
* Очистим массивы <math>B, L, R</math>, удалив все текущие блоки
 
* Очистим массивы <math>B, L, R</math>, удалив все текущие блоки
* Вызовем операцию build
+
* Вызовем операцию <math>\mathrm{build}</math>
  
 
<code>
 
<code>
 
  '''void''' rebuild():
 
  '''void''' rebuild():
    tempA // временная актуальная копия массива <math>A</math>
+
    tempA <font color=green>// временная актуальная копия массива <math>A</math> </font>
    '''for''' i = 0 ... |T| - 1
+
    '''for''' i = 0 ... |T| - 1
            '''for''' j = L[i] ... R[i]
+
        '''for''' j = L[i] ... R[i]
                    tempA.push_back(A[j])
+
            tempA.pushBack(A[j])
    A = tempA
+
    A = tempA
    B.clear()
+
    B.clear()
    L.clear()
+
    L.clear()
    R.clear()
+
    R.clear()
    build()
+
    build()
 
</code>
 
</code>
  
Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math>
+
Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math>.
  
== Операций get ==
+
== Операция get==
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем пытаться выполнять операции только на целых блоках, то есть изменим нашу структуры так, чтобы наш отрезок никогда не попадал в середину блока.
+
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем выполнять операции только на целых блоках, изменим нашу структуры так, чтобы граница отрезка никогда не попадал в середину блока.
  
  
 
Перейдем к реализации:
 
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
+
* Разделим наши блоки при помощи операции <math>\mathrm{split}</math>
 
* Посчитаем операцию на целых блоках использую массив <math>B</math>
 
* Посчитаем операцию на целых блоках использую массив <math>B</math>
  
 
<code>
 
<code>
 
  '''int''' get('''int''' l, '''int''' r):
 
  '''int''' get('''int''' l, '''int''' r):
    result = 0
+
    result = 0
    indexL = split(l – 1)
+
    indexL = split(l – 1)
    indexR = split(r) – 1  
+
    indexR = split(r) – 1  
    for i = indexL ... indexR
+
    '''for''' i = indexL ... indexR
          result = result + B[T[i]]
+
        result = result + B[T[i]]
    return result
+
    '''return''' result
 
</code>
 
</code>
  
Асимптотика: <math>O(split)</math> и <math>O(|T|)</math>. Итого: <math>O(cnt + len)</math>
+
Асимптотика: <math>O(split)</math> и <math>O(|T|)</math>. Итого: <math>O(cnt + len)</math>.
  
 
== Операция erase==
 
== Операция erase==
Пусть получен запрос на выполнение операции удаления числа на позиции <math>x</math>. Аналогично операции get, мы не хотим удалять из середины блока. Когда <math>x</math> является единственным числом в блоке, мы можем просто удалить его из массива <math>T</math>.
+
Пусть получен запрос на выполнение операции удаления числа на позиции <math>x</math>. Аналогично операции <math>get</math>, мы не хотим удалять из середины блока. Когда <math>x</math> является единственным числом в блоке, мы можем просто удалить его из массива <math>T</math>.
  
  
 
Перейдем к реализации:
 
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
+
* Разделим наши блоки при помощи операции <math>\mathrm{split}</math>
 
* Посчитаем операцию на целых блоках использую массив <math>B</math>
 
* Посчитаем операцию на целых блоках использую массив <math>B</math>
  
 
<code>
 
<code>
 
  '''void''' erase('''int''' x):
 
  '''void''' erase('''int''' x):
    split(x - 1)  
+
    split(x - 1)  
    ind = split(x)
+
    ind = split(x)
    T.erase(ind)
+
    T.erase(ind)
 
</code>
 
</code>
  
Асимптотика: <math>O(cnt + len)</math>
+
Асимптотика: <math>O(cnt + len)</math>.
  
  
 
== Операция insert==
 
== Операция insert==
Пусть получен запрос на выполнение вставить число <math>y</math> после числа с индексом <math>x</math>. Аналогично операции get, мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число <math>x</math> в конец массива <math>A</math> и создать новый блок размер <math>1</math>, который ссылается на одно число.
+
Пусть получен запрос на выполнение вставить число <math>y</math> после числа с индексом <math>x</math>. Аналогично операции <math>get</math>, мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число <math>x</math> в конец массива <math>A</math> и создать новый блок размер <math>1</math>, который ссылается на это число.
  
 
Перейдем к реализации:
 
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
+
* Разделим наши блоки при помощи операции <math>\mathrm{split}</math>
 
* Добавим в конец <math>A</math> число <math>y</math>
 
* Добавим в конец <math>A</math> число <math>y</math>
 
* Создадим новый блок и вставим в нужное место
 
* Создадим новый блок и вставим в нужное место
Строка 160: Строка 170:
 
<code>
 
<code>
 
  '''void''' insert('''int''' x, '''int''' y):
 
  '''void''' insert('''int''' x, '''int''' y):
    ind = split(x)
+
    ind = split(x)
    A.push_back(y)
+
    A.pushBack(y)
    indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
+
    indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
    T.insert(ind, indexNewBlock)
+
    T.insert(ind, indexNewBlock)
 
</code>
 
</code>
  
Асимптотика: <math>O(cnt + len)</math>
+
Асимптотика: <math>O(cnt + len)</math>.
 +
 
 +
==См. также==
 +
* [[Дерево отрезков. Построение]]
 +
* [[Многомерное дерево отрезков]]
 +
* [[Статистики на отрезках. Корневая эвристика]]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Дерево отрезков]]

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

Корневая декомпозиция с операциями удаления, вставки в произвольное место и вычисления функции на отрезке.


Описание модификации исходной структуры

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

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

Реализуем две основные операции [math]\mathrm{split}[/math] и [math]\mathrm{rebuild}[/math]. Остальные операции выразим через них. Пусть время работы операции составляет [math]\mathrm{split}[/math] [math]O(cnt + len)[/math] и операции [math]\mathrm{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]\mathrm{rebuild}[/math].

Асимптотика выполнения [math]m[/math] запросов составляет: [math]O\left(\dfrac m k \cdot (n + 4 \cdot k) + m \cdot (len + 4 \cdot k)\right)[/math].

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

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


Построение

Задача:
Пусть дан массив [math]A[/math] размерности [math]n[/math] и [math]m[/math] запросов вида: добавить элемент [math]y[/math] после элемента [math]x[/math], удалить элемент с индексом [math]x[/math], посчитать сумму на отрезке [math][l, r][/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, \ldots, cnt - 1][/math] соответствует порядку [math]B_0, B_1 , \ldots , 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]\mathrm{insert}[/math], [math]\mathrm{erase}[/math], [math]\mathrm{get}[/math]. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс [math]i[/math] называется разрезом, если не существует такого актуального блока, которому принадлежит индекс [math]i[/math] и [math]i + 1[/math] одновременно.

Пусть получен запрос на выполнение операции для индекса [math]x[/math]. Этот индекс входит ровно в один блок массива [math]B[/math], пусть индекс этого блока — [math]ind[/math]. После операции [math]\mathrm{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.pushBack(result)
   L.pushBack(l)
   R.pushBack(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 = createNewBlock(L[ind], x)
   second = createNewBlock(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]\mathrm{rebuild}[/math]. Заметим, что после операций [math]\mathrm{split}[/math] количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб [math]cnt[/math] не стало слишком большим будем полностью перестраивать структуру изменяя [math]cnt[/math] на базовое значение равное [math]cnt = \left\lceil \dfrac{n}{len} \right\rceil[/math].

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


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

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

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

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

Операция get

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


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

  • Разделим наши блоки при помощи операции [math]\mathrm{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]\mathrm{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]\mathrm{split}[/math]
  • Добавим в конец [math]A[/math] число [math]y[/math]
  • Создадим новый блок и вставим в нужное место

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

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

См. также