Корневая декомпозиция с операциями: get, insert, erase — различия между версиями
Josdas (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 14 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Корневая декомпозиция ''' | + | '''Корневая декомпозиция ''' с операциями удаления, вставки в произвольное место и вычисления функции на отрезке. |
− | == | + | == Описание модификации исходной структуры == |
Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент. | Пусть дан массив <math>A</math> размерности <math>n</math> и <math>m</math> запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент. | ||
− | Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию <math>split</math>, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Введем вспомогательную функцию <math>rebuild</math>. Данная функция позволяет вновь перестроить структуру. | + | Будем поддерживать разбиение массива <math>A</math> на блоки. Введем операцию <math>\mathrm{split}</math>, которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на <math>O(1)</math>. Введем вспомогательную функцию <math>\mathrm{rebuild}</math>. Данная функция позволяет вновь перестроить структуру. |
− | Реализуем две основные операции <math>split</math> и <math>rebuild</math>. Остальные операции выразим через них. | + | Реализуем две основные операции <math>\mathrm{split}</math> и <math>\mathrm{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>\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>rebuild</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>O( | + | Асимптотика выполнения <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>. |
− | * для каждого блока сохраним индекс самого левого и самого правого элемента в массивах <math>L, R</math> | + | }} |
− | * результаты подсчета запишем в массив <math>B</math> размерности <math>cnt</math>, где <math>cnt = \left\lceil \dfrac{n}{len} \right\rceil</math> {{---}} количество блоков | + | </noinclude> |
− | * заведем массив <math>T</math>, в котором храним актуальный порядок блоков. <math>T = [0, 1, | + | |
+ | 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>: | Пример реализации построения для операции <math> + </math>: | ||
Строка 30: | Строка 38: | ||
<code> | <code> | ||
'''void''' build(): | '''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> | </code> | ||
− | Построение | + | Построение происходит за <tex>O(n)</tex> времени. |
− | == | + | == Операция split== |
− | Данная операций нужна для реализации операций: <math>insert</math>, <math>erase</math>, <math>get</math>. Она позволяет разделить один блок на два других с целью создания разреза, который необходим в других операциях. Индекс <math>i</math> называется разрезом, если не существует такого актуального блока, которому принадлежит индекс <math>i</math> и <math>i + 1</math> одновременно. | + | Данная операций нужна для реализации операций: <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>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>B, L, R</math> можно только дописывать новую информацию в конце, что соответствует созданию новых блоков. | ||
Строка 57: | Строка 66: | ||
<code> | <code> | ||
− | '''int''' createNewBlock('''int''' l, '''int''' r): // Вспомогательная функция. Позволяет создать блок с <math>l</math> по <math>r</math>. | + | '''int''' createNewBlock('''int''' l, '''int''' r): <font color=green>// Вспомогательная функция. Позволяет создать блок с <math>l</math> по <math>r</math>.</font> |
− | + | result = 0 | |
− | + | '''for''' i = l ... r | |
− | + | result = result + A[i] | |
− | + | B.pushBack(result) | |
− | + | L.pushBack(l) | |
− | + | R.pushBack(r) | |
− | + | cnt++ | |
− | + | '''return''' cnt - 1 | |
</code> | </code> | ||
<code> | <code> | ||
'''int''' split('''int''' x): | '''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) <font color=green>// операций T.erase(x) удаляет элемент под номером x и сдвигает массив T. Время работы <tex>O(|T|)</tex> </font> | |
− | + | T.insert(ind. first) <font color=green>// операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы <tex>O(|T|)</tex> </font> | |
− | + | T.insert(ind + 1, second) | |
− | + | '''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>. | |
− | == | + | == Операция 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>build</math> для построение новой структуры. | + | Будем восстанавливать из актуальных блоков массив <math>A</math>. Потом очищать все текущие блоки, а затем вызывать операцию <math>\mathrm{build}</math> для построение новой структуры. |
Строка 96: | Строка 105: | ||
* Восстановим актуальную версию массива <math>A</math> | * Восстановим актуальную версию массива <math>A</math> | ||
* Очистим массивы <math>B, L, R</math>, удалив все текущие блоки | * Очистим массивы <math>B, L, R</math>, удалив все текущие блоки | ||
− | * Вызовем операцию <math>build</math> | + | * Вызовем операцию <math>\mathrm{build}</math> |
<code> | <code> | ||
'''void''' rebuild(): | '''void''' rebuild(): | ||
− | + | tempA <font color=green>// временная актуальная копия массива <math>A</math> </font> | |
− | + | '''for''' i = 0 ... |T| - 1 | |
− | + | '''for''' j = L[i] ... R[i] | |
− | + | tempA.pushBack(A[j]) | |
− | + | A = tempA | |
− | + | B.clear() | |
− | + | L.clear() | |
− | + | R.clear() | |
− | + | build() | |
</code> | </code> | ||
− | Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math> | + | Асимптотика: заметим, оба циклам суммарно запишут ровно столько элементов, сколько их было в структуре. <math>O(|A| + cnt)</math>. |
− | == | + | == Операция get== |
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем выполнять операции только на целых блоках, изменим нашу структуры так, чтобы граница отрезка никогда не попадал в середину блока. | Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем выполнять операции только на целых блоках, изменим нашу структуры так, чтобы граница отрезка никогда не попадал в середину блока. | ||
Перейдем к реализации: | Перейдем к реализации: | ||
− | * Разделим наши блоки при помощи операции <math>split</math> | + | * Разделим наши блоки при помощи операции <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 | |
− | + | indexL = split(l – 1) | |
− | + | indexR = split(r) – 1 | |
− | + | '''for''' i = indexL ... indexR | |
− | + | result = result + B[T[i]] | |
− | + | '''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== | ||
Строка 138: | Строка 147: | ||
Перейдем к реализации: | Перейдем к реализации: | ||
− | * Разделим наши блоки при помощи операции <math>split</math> | + | * Разделим наши блоки при помощи операции <math>\mathrm{split}</math> |
* Посчитаем операцию на целых блоках использую массив <math>B</math> | * Посчитаем операцию на целых блоках использую массив <math>B</math> | ||
<code> | <code> | ||
'''void''' erase('''int''' x): | '''void''' erase('''int''' x): | ||
− | + | split(x - 1) | |
− | + | ind = split(x) | |
− | + | T.erase(ind) | |
</code> | </code> | ||
− | Асимптотика: <math>O(cnt + len)</math> | + | Асимптотика: <math>O(cnt + len)</math>. |
Строка 155: | Строка 164: | ||
Перейдем к реализации: | Перейдем к реализации: | ||
− | * Разделим наши блоки при помощи операции <math>split</math> | + | * Разделим наши блоки при помощи операции <math>\mathrm{split}</math> |
* Добавим в конец <math>A</math> число <math>y</math> | * Добавим в конец <math>A</math> число <math>y</math> | ||
* Создадим новый блок и вставим в нужное место | * Создадим новый блок и вставим в нужное место | ||
Строка 161: | Строка 170: | ||
<code> | <code> | ||
'''void''' insert('''int''' x, '''int''' y): | '''void''' insert('''int''' x, '''int''' y): | ||
− | + | ind = split(x) | |
− | + | A.pushBack(y) | |
− | + | indexNewBlock = createNewBlock(|A| - 1, |A| - 1) | |
− | + | T.insert(ind, indexNewBlock) | |
</code> | </code> | ||
− | Асимптотика: <math>O(cnt + len)</math> | + | Асимптотика: <math>O(cnt + len)</math>. |
==См. также== | ==См. также== | ||
Строка 173: | Строка 182: | ||
* [[Многомерное дерево отрезков]] | * [[Многомерное дерево отрезков]] | ||
* [[Статистики на отрезках. Корневая эвристика]] | * [[Статистики на отрезках. Корневая эвристика]] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Дерево отрезков]] |
Текущая версия на 19:06, 4 сентября 2022
Корневая декомпозиция с операциями удаления, вставки в произвольное место и вычисления функции на отрезке.
Описание модификации исходной структуры
Пусть дан массив
размерности и запросов вида: посчитать сумму чисел на отрезке, вставить элемент в любую позицию, удалить любой элемент.Будем поддерживать разбиение массива
на блоки. Введем операцию , которая позволяет изменить структуру и разрезать один блок на два других. Такая операция увеличит количество блоков на . Введем вспомогательную функцию . Данная функция позволяет вновь перестроить структуру.Реализуем две основные операции
и . Остальные операции выразим через них. Пусть время работы операции составляет и операции составляет , где — длина блоков, — количество блоков. Ниже будет приведена реализация этих функций с такой асимптотикойВыберем
, тогда после операции будет блоков, где текущие количество элементов в структуре. Заметим, что любая операция добавляет не более, чем новых блоков. После каждых операций вызовем .Асимптотика выполнения
запросов составляет: .Найдем минимум функции, который достигается при
.Итоговое время работы:
.
Построение
Задача: |
Пусть дан массив | размерности и запросов вида: добавить элемент после элемента , удалить элемент с индексом , посчитать сумму на отрезке .
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.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. Время работы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.pushBack(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.pushBack(y) indexNewBlock = createNewBlock(|A| - 1, |A| - 1) T.insert(ind, indexNewBlock)
Асимптотика:
.