Как изменяется асимптотическая сложность алгоритма при использовании частичной суммы?

Question

Использование частичной суммы позволяет сократить время выполнения повторяющихся операций. Предварительное вычисление занимает O(n), а каждый запрос выполняется за O(1). В итоге общая сложность снижается по сравнению с наивными подходами.

YeaHub · Accepted Answer

Частичные суммы — универсальный приём оптимизации для диапазонных запросов.ОпределениеЧастичная сумма (prefix sum) — это массив, где каждый элемент хранит сумму всех предыдущих значений.Как меняется сложностьпостроение массива частичных сумм: O(n),получение суммы диапазона: O(1).Примерprefix[i] = prefix[i - 1] + data[i]

# сумма на отрезке [l, r]
segment_sum = prefix[r] - prefix[l - 1]
Сравнение с наивным подходомбез частичных сумм: O(k) на запрос,с частичными суммами: O(1) на запрос.Практическое применениескользящие окна,аналитические запросы,задачи на диапазоны.ВыводИспользование частичных сумм переводит повторяющиеся операции из линейной сложности в константную за счёт предварительных вычислений.