338
правок
Изменения
м
Через <tex>b_k</tex> обозначим результат предпосчёта в k-ом подотрезке.
Нет описания правки
== Описание ==
=== Предпосчёт ===Пусть нам дан массив <tex>a[0 \ldots A</tex> размерности <tex>n-1]</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> \underbrace{a_0, a_1, \ldots a_{len - 1}}_{b_0}, \ldots \underbrace{a_{len}, \ldots a_{2 len - 1}}_{b_1} , \ldots \underbrace{a_{(cnt - 1) len} \ldots a_{n-1}}_{b_{cnt - 1}} </tex>
Приведем описание для операции минимума:
