Изменения

Пусть мы получили запрос Проверка на извлечение минимума на отрезке то, что блоки входят в отрезок полностью:* для начального блока: <tex> [l \ldots r] ~ mod ~ len = 0</tex>. Отрезок может охватить некоторые блоки ;* для конечного блока: <tex> b (r + 1) ~ mod ~ len = 0 </tex> полностью, и не более двух блоков (начальный и конечный) {{---}} не полностью.

Проверка на тоЗначит, что начальный блок вошел в отрезок не полностью, осуществляется как <tex> l \mod len \neq 0 </tex>. Конечный блок проверяется как <tex> (r + 1) \mod len \neq 0 </tex>. Для для того чтобы найти минимум , например, сумму на отрезке <tex>[l \ldots , r]</tex>, надо найти минимум среди элементов в нам необходимо вручную посчитать сумму на "неполных блокаххвостиках": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>, и минимума среди <tex>b_i</tex> во всех блоках, начиная сложить с k и заканчивая p:<tex>\min_{i = l}^r a_i = \min(\min_{i = l}^{(k + 1)len - 1}(a_i)суммой полных блоков,\min_{i = k}^p( b_i),\min_{i = p + 1}^r (a_i))</tex>предпосчет которых мы сделали заранее.