Корневая декомпозиция


У нас есть задача, о том как быстро считать суммы на отрезке l...r в статичном массиве a за асимптотику меньшую, чем O(n).
Разделим массив a на k блоков одинакового размера и предварительно посчитаем для каждого из них сумму элементов.
Теперь, отвечая на запрос, можно пройтись по элементам массива a и прибавить их к результату, также если один из блоков лежит внутри отрезка, то мы можем прибавить его сумму к результату и пропустить элементы этого блока.
Максимальное количество операций на запрос при таком алгоритме равно n / k + k, следовательно оптимальное k равно квадратному корню из n.
 

Задача для тренировки:

Сумма на отрезке - 1

У нас есть задача, о том как быстро считать суммы на отрезке l...r в массиве a, в котором элементы могут изменяться по одному, за асимптотику меньшую, чем O(n).
Эта задача решается аналогично прошлой, но при запросе изменения необходимо поменять сумму в соответствующем блоке.

Задача для тренировки:

Сумма на отрезке - 2

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

Задача для тренировки:

Умножение на отрезке