Вопрос проверяет понимание влияния предварительных вычислений на общую сложность алгоритма.
Использование частичной суммы позволяет сократить время выполнения повторяющихся операций. Предварительное вычисление занимает O(n), а каждый запрос выполняется за O(1). В итоге общая сложность снижается по сравнению с наивными подходами.
Частичные суммы — универсальный приём оптимизации для диапазонных запросов.
Частичная сумма (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) на запрос.
скользящие окна,
аналитические запросы,
задачи на диапазоны.
Использование частичных сумм переводит повторяющиеся операции из линейной сложности в константную за счёт предварительных вычислений.
