7
правок
Изменения
Новая страница: «'''Корневая декомпозиция ''' {{---}} это подход к реализации ассоциативных операций (например...»
'''Корневая декомпозиция ''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера <tex>n</tex> за <tex> O(\sqrt n)</tex>. Так же есть поддержка операций удаления и вставки в произвольное место
== Идея ==
Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.
Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию split, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Так же будет другая вспомогательная функция rebuild. Данная функция позволяет вновь перестроить структуру.
Реализуем две основные операции split и rebuild. Остальные операции выразим через них.
Пусть время работы операции split: <math>O(cnt + len)</math> и операции rebuild: <math>O(|A| + 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>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>:
<code>
'''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]
</code>
Построение, происходит за <tex>O(n)</tex> времени.
== Операций split ==
Данная операций нужна для реализации операций: reverse, insert, erase. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс <math>i</math> называется разрезом, если не существует такого актуального блока, которому принадлежит индекс <math>i</math> и <math>i + 1</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>T</math>.
Перейдем к реализации:
* Найдем в какой актуальный блок входит <math>x</math>
* Проверим, что <math>x</math> не является разрезом
* Создадим два новых блока. Для каждого из них посчитаем значение функции, а также зададим правильные значения в массивах <math>L</math> и <math>R</math>
* Удалим старый блок из перестановки и запишем туда два других.
<code>
'''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
</code>
<code>
'''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
</code>
Асимптотика: <math>O(cnt)</math> – поиск нужного блока, <math>O(len)</math> – подсчет функции. Итог: <math>O(len + cnt)</math>
Так же заметим, что мы увеличили <math>cnt</math> на <math>2</math>.
== Операций rebuild ==
Вторая необходимая операция – это rebuild. Заметим, что после операций split количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб <math>cnt</math> не стало слишком большим будем полностью перестраивать структуру изменяя <math>cnt</math> на базовое значение равное <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</math>.
Будем восстанавливать из актуальных блоков массив <math>A</math>. Потом очищать все текущие блоки, а затем вызывать операцию build для построение новой структуры.
Перейдем к реализации:
* Восстановим актуальную версию массива <math>A</math>
* Очистим массивы <math>B, L, R</math>, удалив все текущие блоки
* Вызовем операцию build
<code>
'''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()
</code>
Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math>
== Операций get ==
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем пытаться выполнять операции только на целых блоках, то есть изменим нашу структуры так, чтобы наш отрезок никогда не попадал в середину блока.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Посчитаем операцию на целых блоках использую массив <math>B</math>
<code>
'''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
</code>
Асимптотика: <math>O(split)</math> и <math>O(|T|)</math>. Итого: <math>O(cnt + len)</math>
== Операция erase==
Пусть получен запрос на выполнение операции удаления числа на позиции <math>x</math>. Аналогично операции get, мы не хотим удалять из середины блока. Когда <math>x</math> является единственным числом в блоке, мы можем просто удалить его из массива <math>T</math>.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Посчитаем операцию на целых блоках использую массив <math>B</math>
<code>
'''void''' erase('''int''' x):
split(x - 1)
ind = split(x)
T.erase(ind)
</code>
Асимптотика: <math>O(cnt + len)</math>
== Операция insert==
Пусть получен запрос на выполнение вставить число <math>y</math> после числа с индексом <math>x</math>. Аналогично операции get, мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число <math>x</math> в конец массива <math>A</math> и создать новый блок размер <math>1</math>, который ссылается на одно число.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Добавим в конец <math>A</math> число <math>y</math>
* Создадим новый блок и вставим в нужное место
<code>
'''void''' insert('''int''' x, '''int''' y):
ind = split(x)
A.push_back(y)
indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
T.insert(ind, indexNewBlock)
</code>
Асимптотика: <math>O(cnt + len)</math>
== Идея ==
Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.
Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию split, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Так же будет другая вспомогательная функция rebuild. Данная функция позволяет вновь перестроить структуру.
Реализуем две основные операции split и rebuild. Остальные операции выразим через них.
Пусть время работы операции split: <math>O(cnt + len)</math> и операции rebuild: <math>O(|A| + 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>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>:
<code>
'''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]
</code>
Построение, происходит за <tex>O(n)</tex> времени.
== Операций split ==
Данная операций нужна для реализации операций: reverse, insert, erase. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс <math>i</math> называется разрезом, если не существует такого актуального блока, которому принадлежит индекс <math>i</math> и <math>i + 1</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>T</math>.
Перейдем к реализации:
* Найдем в какой актуальный блок входит <math>x</math>
* Проверим, что <math>x</math> не является разрезом
* Создадим два новых блока. Для каждого из них посчитаем значение функции, а также зададим правильные значения в массивах <math>L</math> и <math>R</math>
* Удалим старый блок из перестановки и запишем туда два других.
<code>
'''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
</code>
<code>
'''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
</code>
Асимптотика: <math>O(cnt)</math> – поиск нужного блока, <math>O(len)</math> – подсчет функции. Итог: <math>O(len + cnt)</math>
Так же заметим, что мы увеличили <math>cnt</math> на <math>2</math>.
== Операций rebuild ==
Вторая необходимая операция – это rebuild. Заметим, что после операций split количество блоков увеличивалось, а работа всех функций зависит от этого числа. Для того чтоб <math>cnt</math> не стало слишком большим будем полностью перестраивать структуру изменяя <math>cnt</math> на базовое значение равное <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</math>.
Будем восстанавливать из актуальных блоков массив <math>A</math>. Потом очищать все текущие блоки, а затем вызывать операцию build для построение новой структуры.
Перейдем к реализации:
* Восстановим актуальную версию массива <math>A</math>
* Очистим массивы <math>B, L, R</math>, удалив все текущие блоки
* Вызовем операцию build
<code>
'''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()
</code>
Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math>
== Операций get ==
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем пытаться выполнять операции только на целых блоках, то есть изменим нашу структуры так, чтобы наш отрезок никогда не попадал в середину блока.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Посчитаем операцию на целых блоках использую массив <math>B</math>
<code>
'''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
</code>
Асимптотика: <math>O(split)</math> и <math>O(|T|)</math>. Итого: <math>O(cnt + len)</math>
== Операция erase==
Пусть получен запрос на выполнение операции удаления числа на позиции <math>x</math>. Аналогично операции get, мы не хотим удалять из середины блока. Когда <math>x</math> является единственным числом в блоке, мы можем просто удалить его из массива <math>T</math>.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Посчитаем операцию на целых блоках использую массив <math>B</math>
<code>
'''void''' erase('''int''' x):
split(x - 1)
ind = split(x)
T.erase(ind)
</code>
Асимптотика: <math>O(cnt + len)</math>
== Операция insert==
Пусть получен запрос на выполнение вставить число <math>y</math> после числа с индексом <math>x</math>. Аналогично операции get, мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число <math>x</math> в конец массива <math>A</math> и создать новый блок размер <math>1</math>, который ссылается на одно число.
Перейдем к реализации:
* Разделим наши блоки при помощи операции split
* Добавим в конец <math>A</math> число <math>y</math>
* Создадим новый блок и вставим в нужное место
<code>
'''void''' insert('''int''' x, '''int''' y):
ind = split(x)
A.push_back(y)
indexNewBlock = createNewBlock(|A| - 1, |A| - 1)
T.insert(ind, indexNewBlock)
</code>
Асимптотика: <math>O(cnt + len)</math>
