Всем доброго времени суток!
Не знаю, как подступиться к этой теме, поэтому сразу начнем с примера.
Как это можно сделать? Давайте будем разбираться...
Первая мысль
Ну, проще всего заюзать питоновские функции.
А вообще, если вы не знаете эти функции, то можете сами что-нибудь забацать. Например это:
Первый и второй алгоритмы работают со сложностью O(n), n = r - l + 1 (длина отрезка).
Усложним задачу
А теперь представьте, что вам нужно посчитать сумму на отрезке очень-очень много раз, ну, скажем, 10 000 раз для массива размером 100 000, тогда в худшем случае нам придется выполнить 10e9 операций. Это плохо... Как бы ускорить подсчет суммы на отрезке...
Но сначала, что такое префикс и суффикс.
Префикс - это подмассив с 0 до p.
Суффикс - подмассив с s до len(lst) - 1.
Слушайте... А что если мы рассмотрим префикс массива до l - 1 и до r.
Кажется, сумма на зеленом префиксе минус сумма на синем будет равна сумме на отрезке... Да? Даа!
Как посчитать сумму на префиксе... очень просто, думаю вы и так это сможете это сделать!
Мы можем запомнить все суммы на префиксах в массиве s, в котором s[p] = sum(a[:p + 1]).
Чему теперь будет равна сумма от l до r (sum(lst[l: r + 1]))?
Мы считаем это за O(1), понимаете? Это победа... только не забудьте проверить крайние значения индексов...
Если вы не до конца поняли, что мы сделали, посмотрите внимательно на картинку с экселем :)
Такие дела... Что-то аналогичное можно сделать и с суффиксами. Просто считать нужно будет с конца.
Еще задачка
Теперь нам нужно быстро отвечать на запросы: "Сколько элементов больших V = const на отрезке от l до r?"
Ну, по аналогии делаем... хихи))
Вывод
Вообще, мы можем применять этот метод всегда, когда речь идет об операции, имеющей обратную (+-, */)... вроде....
Ну вот и все
Будте счастливы! Покасики!!
