Пусть мы получили запрос на нахождение суммы (минимума/максимума и т.д) на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
Проверка на тоТаким образом, что блоки входят в отрезок полностью:* для начального блока: того чтобы найти, например, сумму на отрезке <tex>[l ~ mod ~ len = 0</tex> ;* для конечного блока: <tex>(, r + 1) ~ mod ~ len = 0 ]</tex>нам необходимо вручную посчитать сумму на "хвостиках" и сложить с суммой полных блоков, предпосчет которых мы сделали заранее.
Значит, для того чтобы найти, например, сумму Пример обработки запроса "подсчет суммы на отрезке <tex>[l, r]</tex> нам необходимо вручную посчитать сумму на "хвостиках" и сложить с суммой полных блоков, предпосчет которых мы сделали заранее.:<pre>left = l / lenright = r / lenend = (left + 1) * len - 1sum = 0 if left == right for i = l to r sum += a[i]else for i = l to end sum += a[i] for i = left + 1 to right - 1 sum += b[i] for i = right * len to r sum += a[i]</pre>
=== Изменение элемента ===
