Изменения
Нет описания правки
Выберем <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>.
