0Pricing
Coding Interview Prep · Урок

Префиксные суммы и текущие итоги

Создавайте массивы префиксных сумм для запросов сумм на диапазоне за O(1) и применяйте этот приём к задачам о подмассивах, например к поиску подмассива с максимальной суммой

«Префиксные суммы и текущие итоги» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Задача о сумме диапазона

Для данного массива nums требуется отвечать на многочисленные запросы вида: какова сумма элементов с индекса i по индекс j? Наивное вычисление каждого запроса занимает O(n) времени, поэтому k запросов требуют O(n×k). С помощью массива префиксных сумм можно за O(n) предварительно вычислить нарастающий итог, а затем отвечать на каждый запрос за O(1). Это один из наиболее часто используемых методов предварительных вычислений на собеседованиях.

# Naive: O(n) per query
def range_sum_naive(nums, i, j):
    return sum(nums[i:j+1])

nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3))  # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4))  # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations

Построение массива префиксных сумм

Определите prefix[i] как сумму от nums[0] до nums[i-1] включительно (одна дополнительная позиция и смещение с нулевой индексацией на 1 упрощают обработку граничных случаев). Постройте массив за O(n) одним проходом: prefix[i] = prefix[i-1] + nums[i-1]. Тогда запрос диапазона sum(i, j) превращается в prefix[j+1] - prefix[i]: одно вычитание за O(1).

def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix, i, j):
    return prefix[j+1] - prefix[i]  # O(1)

nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre)                    # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3))  # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15  correct
print(range_sum(pre, 1, 3))  # 15

Сумма подмассива равна K

Поиск количества подмассивов с суммой, равной k, — классическая задача на хеш-таблицу и префиксные суммы. Ключевая идея: сумма подмассива от i до j равна prefix[j] - prefix[i-1]. Если мы хотим, чтобы она была равна k, то prefix[i-1] = prefix[j] - k. При проходе слева направо с поддержанием текущей префиксной суммы мы проверяем, сколько раз ранее встречалось значение current_sum - k, и за общее время O(n) считаем все подходящие подмассивы.

from collections import defaultdict

def subarray_sum_k(nums, k):
    count = 0
    current = 0
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix
    for n in nums:
        current += n
        count += freq[current - k]  # how many prior sums give diff=k
        freq[current] += 1
    return count

print(subarray_sum_k([1, 1, 1], 2))    # 2
print(subarray_sum_k([1, 2, 3], 3))    # 2  ([1,2] and [3])

Максимальная сумма подмассива с помощью префиксных сумм

Максимальную сумму подмассива можно представить как задачу на префиксные суммы: для каждого индекса j нужно максимизировать prefix[j] - prefix[i] по всем i < j. Оптимальным i для каждого j будет минимальная префиксная сумма, встреченная ранее. Проход слева направо с отслеживанием min_prefix даёт время O(n). Это эквивалент алгоритма Кадане, рассмотренный с точки зрения префиксных сумм.

def max_subarray_prefix(nums):
    max_sum  = float('-inf')
    min_pre  = 0  # prefix[0] = 0
    current  = 0
    for n in nums:
        current += n
        max_sum = max(max_sum, current - min_pre)
        min_pre = min(min_pre, current)
    return max_sum

print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6  (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1

Двумерные префиксные суммы для запросов к сетке

Префиксные суммы распространяются и на двумерные сетки. Определите P[i][j] как сумму всех элементов в прямоугольнике от (0,0) до (i-1,j-1). Постройте её по формуле включений и исключений: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. После этого на любой запрос суммы прямоугольника от (r1,c1) до (r2,c2) можно ответить за O(1) с помощью четырёх обращений к массиву.

def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    P = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            P[r][c] = (P[r-1][c] + P[r][c-1]
                       - P[r-1][c-1] + grid[r-1][c-1])
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1))  # 3+0+5+6 = 14

Нарастающий итог для индекса равновесия

Индекс равновесия — это позиция, в которой сумма элементов слева равна сумме элементов справа. Сначала вычислите общую сумму, затем проходите массив, поддерживая нарастающую сумму слева. Сумма справа равна total - left_sum - nums[i]. Проверяйте равенство за O(1) для каждого индекса, получая общую сложность O(n). Это показывает, как нарастающий итог заменяет два отдельных массива префиксных сумм.

def find_pivot_index(nums):
    total = sum(nums)
    left_sum = 0
    for i, n in enumerate(nums):
        # right_sum = total - left_sum - nums[i]
        if left_sum == total - left_sum - n:
            return i
        left_sum += n
    return -1

print(find_pivot_index([1, 7, 3, 6, 5, 6]))  # 3
print(find_pivot_index([1, 2, 3]))             # -1

Массив произведений всех элементов, кроме текущего

Для данного массива верните массив, в котором каждый элемент равен произведению всех остальных элементов. Деление запрещено. Используйте префиксное произведение и суффиксное произведение: элемент результата в позиции i равен произведению всех элементов до i, умноженному на произведение всех элементов после i. Постройте префиксные произведения проходом слева направо, затем умножайте на суффиксные произведения проходом справа налево, используя нарастающую переменную — дополнительный массив для суффикса не нужен.

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    # Left pass: result[i] = product of nums[:i]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # Right pass: multiply in product of nums[i+1:]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6]   O(n) time, O(1) extra space

Префиксная сумма по модулю

Некоторые задачи требуют найти количество подмассивов, сумма которых делится на k. Используйте префиксные суммы по модулю k: если prefix[j] % k == prefix[i] % k, то sum(i+1..j) делится на k. Хеш-таблица, подсчитывающая каждое значение остатка по мере прохода, обеспечивает время O(n). Важно инициализировать её так: freq[0] = 1, чтобы обрабатывать подмассивы, начинающиеся с индекса 0.

from collections import defaultdict

def subarray_div_by_k(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    current = 0
    count = 0
    for n in nums:
        current = (current + n) % k
        count += freq[current]
        freq[current] += 1
    return count

print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7  (seven subarrays divisible by 5)

Массив разностей для обновлений диапазона

Массив разностей — это обратное преобразование префиксной суммы. Для данного массива предварительно вычислите diff[i] = nums[i] - nums[i-1]. Добавление x к диапазону [l, r] требует всего двух операций O(1) над массивом разностей: diff[l] += x и diff[r+1] -= x. После всех обновлений восстановите результирующий массив одним проходом вычисления префиксных сумм. Это превращает k обновлений диапазонов из O(n×k) в O(n + k).

def apply_range_updates(n, updates):
    # updates: list of (l, r, val)
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l]   += val
        diff[r+1] -= val
    # Reconstruct with prefix sum
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]

Префиксные суммы в задачах на собеседованиях

Префиксные суммы встречаются во многих категориях задач:

  • Запросы диапазона — сумма подмассива, сумма прямоугольника
  • Подсчёт подмассивов — сумма равна k, сумма делится на k
  • Задачи на произведения — произведение всех элементов, кроме текущего
  • Равновесие — поиск индекса равновесия
  • Обновления диапазона — массив разностей
Увидев задачу с накопительными суммами или агрегированием по диапазонам, сначала подумайте о префиксных суммах. Это почти всегда позволяет получить решение за O(n) вместо наивного полного перебора за O(n²).

# Template: prefix sum + hash map for subarray problems
from collections import defaultdict

def subarray_count_template(nums, target):
    """
    Count subarrays with property involving prefix sums.
    Adapt 'target' and lookup condition for each problem.
    """
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix at sum=0
    current = 0
    count = 0
    for n in nums:
        current += n
        count += freq[current - target]  # adjust per problem
        freq[current] += 1
    return count

print(subarray_count_template([1,2,3,2,1], 3))  # 3

Нарастающая сумма и нарастающий максимум

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

def max_profit(prices):
    # Running minimum buy price
    min_price = float('inf')
    max_prof  = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_prof:
            max_prof = price - min_price
    return max_prof

def left_max_array(heights):
    # Running max from left for trapping rain water
    n = len(heights)
    left_max = [0] * n
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], heights[i])
    return left_max

print(max_profit([7,1,5,3,6,4]))  # 5

Быстрая проверка

Проверьте, насколько вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке вы узнали: префиксные суммы превращают запросы диапазона за O(n) в обращения за O(1), предварительно вычисляя накопительные суммы за один проход O(n), сочетание префиксных сумм с хеш-таблицей позволяет за O(n) считать подмассивы с заданной суммой или свойством делимости, а массивы разностей являются обратным преобразованием: они позволяют выполнять обновления диапазона за O(1) с одним проходом восстановления по префиксным суммам в конце. Далее мы перейдём к технике двух указателей, начиная с указателей на противоположных концах.

Часто задаваемые вопросы

Урок «Префиксные суммы и текущие итоги» бесплатный?

Да — полный текст урока «Префиксные суммы и текущие итоги» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Префиксные суммы и текущие итоги»?

Создавайте массивы префиксных сумм для запросов сумм на диапазоне за O(1) и применяйте этот приём к задачам о подмассивах, например к поиску подмассива с максимальной суммой Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Префиксные суммы и текущие итоги»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Основы массивов и операции на месте
  2. Префиксные суммы и текущие итоги
  3. Два указателя: от противоположных концов
  4. Два указателя: медленный и быстрый
← Назад к Coding Interview Prep