338
правок
Изменения
м
Приведем описание для операции минимума:
→Предпосчёт
== Описание ==
=== Предпосчёт Предпосчет ===[[Файл:sqrt.png|right|540px]]Пусть нам дан массив <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> — количество блоков.
Пример предпосчета для запроса о подсчете суммы:<texpre> \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_{for(cnt - 1int i = 0; i < n; i++) B[i / len} \ldots a_{n-1}}_{b_{cnt - 1}} ] += A[i]</texpre>
=== Запрос ===
