Изменения

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

Пусть нам дан массив <tex>A</tex> размерности <tex>n</tex>. Cделаем следующие действия:

* разделим массив <tex>A</tex> на блоки длины <tex>len = \lfloor \sqrt{n} \rfloor</tex> ;

* результаты подсчета запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков.

Пример реализации построения массива <tex>B</tex> для операции <tex> \circ </tex>:

== Обработка запроса ==

Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.

Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.

Пример реализации обработки запроса:

== Запрос на изменение элемента ==

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

* если оба условия выполняются, то запрос на изменение элемента мы можем сделать за <tex>O(1)</tex> времени;

* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.

Примеры реализации: