❓ Что такое префиксная сумма и где её использовать

Префиксная сумма это массив, где каждый элемент prefix[i] хранит сумму всех элементов исходного массива от 0 до i включительно.

Построение:

func buildPrefix(arr []int) []int {
    prefix := make([]int, len(arr)+1)
    for i, v := range arr {
        prefix[i+1] = prefix[i] + v
    }
    return prefix
}

func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

Задача: количество подмассивов с суммой K

func subarraySum(nums []int, k int) int {
    count := 0
    prefix := 0
    seen := map[int]int{0: 1}

    for _, v := range nums {
        prefix += v
        count += seen[prefix-k] // если ключа нет — вернёт 0, это фича Go
        seen[prefix]++
    }

    return count
}

Где использовать:

• Запросы суммы на отрезке — самый очевидный случай. Если массив не меняется, а запросов много, строишь префикс один раз и отвечаешь за O(1).

• Поиск подмассива с заданной суммой — сводишь к задаче "найти два индекса префикса с разностью K", решается через хэшмап за O(n).

• Задачи на чётность/нечётность суммы — считаешь префикс по модулю 2, ищешь совпадения.

• Задачи на матрицах — 2D префикс даёт сумму любого прямоугольника за O(1), используется в задачах с изображениями, тепловыми картами, grid-задачах.

• Sliding window с условием на сумму — иногда проще через префикс, чем двумя указателями, особенно если окно не фиксированное.

🐸 Библиотека Go для собеса