1632
правки
Изменения
м
Задача:
<includeonly>{{#if: {{{neat|}}}|
<div style="background-color: #fcfcfc; float:left;">
<div style="background-color: #ddd;">'''Задача:'''</div>
<div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div>
</div>|
<table border="0" width="100%">
<tr><td style="background-color: #ddd">'''Задача:'''</td></tr>
<tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr>
</table>}}
</includeonly>
rollbackEdits.php mass rollback
Выберем <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>.
== Построение ==
<noinclude>
{{Задача
|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делаем следующие действия:
</code>
Построение, происходит за <tex>O(n)</tex> времени.
== Операция <math>\mathrm{split}</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>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> можно только дописывать новую информацию в конце, что соответствует созданию новых блоков.
'''if''' L[ind] == x '''or''' R[ind] == x '''or''' x < 0
'''return''' 0
first = createNewBolockcreateNewBlock(L[ind], x) second = createNewBolockcreateNewBlock(x, R[ind]) T.erase(ind) <font color=green>// операций T.erase(x) удаляет элемент под номером x и сдвигает массив T. Время работы <mathtex>O(|T|)</mathtex> </font> T.insert(ind. first) <font color=green>// операций T.insert(x, y) вставляет в массив T после индекса x значение y и сдвигает массив. Время работы <mathtex>O(|T|)</mathtex> </font>
T.insert(ind + 1, second)
'''return''' ind
Также заметим, что мы увеличили <math>cnt</math> на <math>2</math>.
== Операция <math>\mathrm{rebuild}</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>O(|A| + cnt)</math>.
== Операция <math>\mathrm{get}</math>==
Пусть получен запрос на выполнение операции на отрезке <math>[l, r]</math>. Будем выполнять операции только на целых блоках, изменим нашу структуры так, чтобы граница отрезка никогда не попадал в середину блока.
Асимптотика: <math>O(split)</math> и <math>O(|T|)</math>. Итого: <math>O(cnt + len)</math>.
== Операция <math>\mathrm{erase}</math>==
Пусть получен запрос на выполнение операции удаления числа на позиции <math>x</math>. Аналогично операции <math>get</math>, мы не хотим удалять из середины блока. Когда <math>x</math> является единственным числом в блоке, мы можем просто удалить его из массива <math>T</math>.
== Операция <math>\mathrm{insert}</math>==
Пусть получен запрос на выполнение вставить число <math>y</math> после числа с индексом <math>x</math>. Аналогично операции <math>get</math>, мы не хотим вставлять в середину блока. Когда нужно вставить на границу блока, то мы можем просто добавить число <math>x</math> в конец массива <math>A</math> и создать новый блок размер <math>1</math>, который ссылается на это число.
