Split-rebuild

Материал из Algocode wiki
Версия от 12:23, 28 сентября 2020; KiKoS (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Простое разделение на блоки позволяет создать достаточно мощную структуру, которая позволяет делать операции вставки, удаления и подсчета некоторых функций на отрезках за корень. Рассмотрим задачу подробнее.

Постановка задачи

Пусть дан массив из $N$ элементов. К нему поступает $M$ запросов трех видов:

  • Вставить элемент $x$ на позицию $i$, то есть слева от него окажется ровно $i$ элмементов;
  • Удалить элемент с позиции $i$;
  • Найти минимум на полуинтервале $[l, r)$.

Будем считать, что все индексы начинаются с нуля.

Решение с помощью корневой декомпозиции

Основная идея решения: разделим массив примерно на $\sqrt{N}$ частей одинакового размера. Будем поддерживать глобальный счетчик OPERATIONS_COUNTER, равный числу операций изменения, произведенных над структурой.

Вставка

При вставке будем явно вставлять элемент в нужный блок. Если вставка происходит на границе блоков, то договоримся вставлять элемент в единственный существующий блок, если вставка производится в самый конец или в самое начало. Иначе вставляем в блок, найденный функцией findBlock. Можно сделать иначе при вставке на концах - вставлять в новый блок, создавая его. Этот случай будет лучше работать, если у нас происходит много вставок подряд, а предыдущий способ - когда больше надо отвечать на запросы. Можно также принимать решение о вставке тем или иным способом случайно. Это решение, наверное, будет наиболее универсальным и применимым.

 1 void insert(int pos, int elem) {
 2     OPERATIONS_COUNTER++;
 3     if (blocks.empty()) {
 4         blocks.resize(1);
 5         blocks[0].push_back(elem);
 6         return;
 7     }
 8     pair<int, int> posBlock = findPosition(pos);
 9     if (posBlock.first == blocks.size()) {
10         blocks.back().push_back(elem);
11         return;
12     }
13     blocks[posBlocks.first].insertAtPosition(posBlock.second, elem);

Удаление

При удалении будем явно удалять элемент из блока за размер блока. Если блок оказался пустым, то ничего с ним не будем делать пока что.

Функция на полуинтервале

Запрос о вычислении функции обрабатываем, как в обычной простой корневой декомпозиции.

Перестраивание

Чтобы на допускать создания слишком большого числа маленьких блоков или разрастания отдельных блоков, раз в $\sqrt{N}$ операций будем заново полностью перестраивать структуру. Размер блока при этом тоже будет меняться. Также будем всегда поддерживать размер всей структуры. Мало ли, может пригодиться.

Предположим, что массив блоков хранится как глобальный вектор blocks.

 1 void rebuild() {
 2     int newBlockSize = sqrt(size) + 1;
 3     vector<int> all;
 4     for (auto& block : blocks) {
 5         for (auto elem : block) {
 6             all.push_back(elem);
 7         }
 8     }
 9     blocks.clear();
10     int newBlockNumber = (totalSize + newBlockSize - 1) / newBlockSize;
11     blocks.resize(totalSize);
12     for (int i = 0; i < totalSize; i++) {
13         blocks[i / newBLockSize].push_back(all[i]);
14         updateFunction(i);
15     }
16 }

Как искать нужный блок

Так как теперь мы не можем гарантировать, что блок имеет фиксированный размер в каждый момент времени, то находить нужное место будем просто проходом по массиву блоков. Функция возвращает номер блока и позицию именно в нем.

 1 pair<int, int> findBlock(int pos) {
 2     if (blocks.empty() || pos == 0) {
 3         return {0, 0};
 4     }
 5     int byLeft = 0;
 6     int i = 0;
 7     while (i < blocks.size() && byLeft < pos) {
 8         byLeft += blocks[i].size();
 9         i++;
10     }
11     i--;
12     byLeft -= blocks[i].size();
13     return {i, pos - byLeft};
14 }



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s