338
правок
Изменения
м
→Предпосчет
Пусть нам дан массив <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> — количество блоков.
