|
Вкратце о том, что из себя представляет задача на запрос по диапазону: дан массив a из n элементов, дано кол-во запросов q. Для каждого запроса даны границы l, r такие, что 1 ≤ l ≤ r ≤ n.
Требуется для каждого запроса найти максимум/минимум/сумму/НОД и проч. среди элементов a(l), a(l + 1) … a(r - 1), a(r).
Предположим, мы имеем массив длины n = 105 и кол-во запросов q = 105. Если искать максимум/сумму и проч. в массиве «наивным» методом, асимптотическая сложность которого O(n), в задаче на обработку запросов мы будем иметь сложность O(nq), что в данном случае – 1010. При том, что современные ЭВМ обрабатывают 108 о/с, данное решение не является оптимальным. |
Главная 
