Вставки, удаления и перестроение

Обычная корневая делит массив на блоки фиксированной длины. Как только появляются вставки в середину, это перестаёт работать: сдвигается всё, что правее.

Лечение простое: хранить блоки как список массивов переменной длины.

std::vector<std::vector<int>> blocks;   // blocks[b] - содержимое b-го блока

Вставка

Находим блок, в который попадает нужная позиция, - проходом по блокам, суммируя длины. Вставляем элемент в его вектор.

Оба шага стоят $O(\sqrt{n})$: блоков около $\sqrt{n}$, и внутри блока сдвиг тоже $O(\sqrt{n})$.

int b = 0;
while (b < (int)blocks.size() && at >= (int)blocks[b].size()) { at -= blocks[b].size(); b++; }
blocks[b].insert(blocks[b].begin() + at, value);

Перестроение

Беда в том, что блок распухает: если все вставки идут в одно место, один блок вырастет до $n$, и запрос к нему станет линейным.

Лекарство - перестроение: когда какой-нибудь блок стал слишком большим, разложить все элементы заново по блокам длины $\sqrt{n}$.

if ((int)blocks[b].size() > 2 * B) rebuildAll();

Перестроение стоит $O(n)$, но случается редко: чтобы блок вырос вдвое, в него нужно вставить $B$ элементов. Значит, между двумя перестроениями проходит не меньше $B = \sqrt{n}$ операций, и амортизированная цена перестроения - $O(n / \sqrt{n}) = O(\sqrt{n})$.

Тот же порядок, что у самой вставки, - то есть перестроение бесплатно в смысле асимптотики.

Другой способ: перестраивать по счётчику

Ещё проще - не следить за размерами блоков вовсе, а перестраивать всё каждые $\sqrt{n}$ операций. Тогда ни один блок не успеет вырасти больше чем на $\sqrt{n}$ элементов, и оценка та же.

Этот вариант короче и не требует думать о том, какой блок распух. Цена - лишние перестроения там, где вставки были равномерными.

Удаление

Симметрично: находим блок, стираем элемент из вектора. Пустые блоки лучше выбрасывать, иначе их накопится много и проход по блокам перестанет быть $O(\sqrt{n})$.

Это тот случай, когда корневая делает то, чего дерево отрезков не умеет вовсе: менять количество элементов. Обычное дерево отрезков строится на фиксированном наборе позиций; чтобы разрешить вставки, нужно неявное дерево, а это заметно больше кода.