MidПрактика12 min

Prefix Sum

Префиксные суммы: одномерные и двумерные, решение задач на подмассивы

AlgoArrays and strings

Prefix Sum (Префиксные суммы)

Идея

Prefix Sum — это предварительно вычисленный массив, где prefix[i] хранит сумму элементов от начала до индекса i. Это позволяет вычислить сумму любого подмассива за O(1).

Исходный:  [2, 4, 1, 3, 5]
Префикс:   [0, 2, 6, 7, 10, 15]
             ^                ^
          prefix[0]=0     prefix[5]=15 (сумма всех)

Сумма arr[1..3] = prefix[4] - prefix[1] = 10 - 2 = 8
Проверка: 4 + 1 + 3 = 8 ✓

Формула

prefix[0] = 0
prefix[i] = prefix[i-1] + arr[i-1]

Сумма arr[left..right] = prefix[right+1] - prefix[left]

Построение и использование

function buildPrefixSum(array $arr): array
{
    $n = count($arr);
    $prefix = array_fill(0, $n + 1, 0);
    for ($i = 0; $i < $n; $i++) {
        $prefix[$i + 1] = $prefix[$i] + $arr[$i];
    }
    return $prefix;
}

function rangeSum(array $prefix, int $left, int $right): int
{
    // Sum of elements from left to right inclusive
    return $prefix[$right + 1] - $prefix[$left];
}

// Example
$arr = [3, 1, 4, 1, 5, 9, 2, 6];
$prefix = buildPrefixSum($arr);
// prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]

echo rangeSum($prefix, 2, 5);  // arr[2]+arr[3]+arr[4]+arr[5] = 4+1+5+9 = 19
// prefix[6] - prefix[2] = 23 - 4 = 19 ✓
**Построение:** O(n). **Запрос суммы:** O(1).

Сравни с наивным подходом:

Подход Построение Запрос суммы
Наивный O(1) O(n)
Prefix Sum O(n) O(1)

Prefix Sum выгоден, когда запросов много (больше n).

Задача 1: Subarray Sum Equals K

Условие: посчитать количество подмассивов с суммой равной k.

function subarraySum(array $nums, int $k): int
{
    $count = 0;
    $prefixSum = 0;
    // Stores: prefixSum -> how many times it occurred
    $prefixCount = [0 => 1];

    foreach ($nums as $num) {
        $prefixSum += $num;

        // If prefixSum - k was seen before,
        // then there is a subarray with sum k
        if (isset($prefixCount[$prefixSum - $k])) {
            $count += $prefixCount[$prefixSum - $k];
        }

        $prefixCount[$prefixSum] = ($prefixCount[$prefixSum] ?? 0) + 1;
    }

    return $count;
}

// nums = [1, 1, 1], k = 2
// prefixSum: 0, 1, 2, 3
// Step 1: ps=1, 1-2=-1 not found, count=0
// Step 2: ps=2, 2-2=0 found(1 time), count=1
// Step 3: ps=3, 3-2=1 found(1 time), count=2
// Answer: 2 (subarrays [1,1] and [1,1])
Визуализация для `[1, 2, 3], k = 3`: 
Индекс:        0    1    2
Элемент:       1    2    3
Prefix Sum: 0  1    3    6

prefixCount = {0: 1}

i=0: ps=1, ps-k=1-3=-2 нет.     count=0, {0:1, 1:1}
i=1: ps=3, ps-k=3-3=0 есть!     count=1, {0:1, 1:1, 3:1}
i=2: ps=6, ps-k=6-3=3 есть!     count=2, {0:1, 1:1, 3:1, 6:1}

Подмассивы: [1,2] и [3]

Задача 2: Pivot Index

Условие: найти индекс, где сумма слева = сумме справа.

function pivotIndex(array $nums): int
{
    $total = array_sum($nums);
    $leftSum = 0;

    for ($i = 0; $i < count($nums); $i++) {
        $rightSum = $total - $leftSum - $nums[$i];
        if ($leftSum === $rightSum) {
            return $i;
        }
        $leftSum += $nums[$i];
    }

    return -1;
}

// [1, 7, 3, 6, 5, 6]
// total = 28
// i=0: left=0, right=28-0-1=27. 0!=27
// i=1: left=1, right=28-1-7=20. 1!=20
// i=2: left=8, right=28-8-3=17. 8!=17
// i=3: left=11, right=28-11-6=11. 11==11! -> return 3
## Задача 3: Product of Array Except Self

Условие: для каждого элемента — произведение всех остальных (без деления).

function productExceptSelf(array $nums): array
{
    $n = count($nums);
    $result = array_fill(0, $n, 1);

    // Prefix product (left to right)
    $leftProduct = 1;
    for ($i = 0; $i < $n; $i++) {
        $result[$i] = $leftProduct;
        $leftProduct *= $nums[$i];
    }

    // Suffix product (right to left)
    $rightProduct = 1;
    for ($i = $n - 1; $i >= 0; $i--) {
        $result[$i] *= $rightProduct;
        $rightProduct *= $nums[$i];
    }

    return $result;
}

// nums = [1, 2, 3, 4]
// Left pass: result = [1, 1, 2, 6]
//   result[0]=1, result[1]=1, result[2]=1*2=2, result[3]=1*2*3=6
// Right pass: result = [24, 12, 8, 6]
//   result[3]=6*1=6, result[2]=2*4=8, result[1]=1*12=12, result[0]=1*24=24
## Двумерные префиксные суммы (2D Prefix Sum)

Для матриц: быстрый запрос суммы в прямоугольной области.

Матрица:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

Prefix 2D (включая нулевую строку/столбец):
[0,  0,  0,  0]
[0,  1,  3,  6]
[0,  5, 12, 21]
[0, 12, 27, 45]

prefix[i][j] = сумма всех элементов в прямоугольнике (0,0)-(i-1,j-1)

Построение

function build2dPrefix(array $matrix): array
{
    $rows = count($matrix);
    $cols = count($matrix[0]);
    $prefix = [];
    for ($i = 0; $i <= $rows; $i++) {
        $prefix[$i] = array_fill(0, $cols + 1, 0);
    }

    for ($i = 1; $i <= $rows; $i++) {
        for ($j = 1; $j <= $cols; $j++) {
            $prefix[$i][$j] = $matrix[$i - 1][$j - 1]
                            + $prefix[$i - 1][$j]
                            + $prefix[$i][$j - 1]
                            - $prefix[$i - 1][$j - 1];
        }
    }

    return $prefix;
}
Визуализация формулы: 
prefix[i][j] = matrix[i-1][j-1] + A + B - C

+-------+---+
|   C   | B |
+-------+---+
|   A   | X | <- matrix[i-1][j-1]
+-------+---+

A = prefix[i][j-1]     (всё левее)
B = prefix[i-1][j]     (всё выше)
C = prefix[i-1][j-1]   (пересечение, вычитаем чтобы не считать дважды)

Запрос суммы прямоугольника

function rangeSum2d(array $prefix, int $r1, int $c1, int $r2, int $c2): int
{
    // Sum in rectangle (r1,c1) - (r2,c2) inclusive
    return $prefix[$r2 + 1][$c2 + 1]
         - $prefix[$r1][$c2 + 1]
         - $prefix[$r2 + 1][$c1]
         + $prefix[$r1][$c1];
}
Визуализация: 
Нужна сумма в области X:

+-------+-------+---+
|   D   |   C   |   |
+-------+-------+---+
|   B   |   X   |   |  <- (r1,c1) до (r2,c2)
+-------+-------+---+
|       |       |   |
+-------+-------+---+

sum(X) = prefix[r2+1][c2+1] - C - B + D
       = total - top - left + overlap

Полный пример

$matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
];

$prefix = build2dPrefix($matrix);

// Sum of rectangle (1,1) to (2,2): 5+6+8+9 = 28
echo rangeSum2d($prefix, 1, 1, 2, 2);  // 28

// Sum of entire matrix (0,0) to (2,2): 1+2+3+4+5+6+7+8+9 = 45
echo rangeSum2d($prefix, 0, 0, 2, 2);  // 45
## Задача 4: Подмассив с суммой, делящейся на k 
function subarraysDivisibleByK(array $nums, int $k): int
{
    $count = 0;
    $prefixSum = 0;
    $remainderCount = [0 => 1];

    foreach ($nums as $num) {
        $prefixSum += $num;
        $remainder = $prefixSum % $k;

        // Normalize for negative numbers
        if ($remainder < 0) {
            $remainder += $k;
        }

        if (isset($remainderCount[$remainder])) {
            $count += $remainderCount[$remainder];
        }

        $remainderCount[$remainder] = ($remainderCount[$remainder] ?? 0) + 1;
    }

    return $count;
}

// If two prefix sums have the same remainder when divided by k,
// the subarray between them is divisible by k.
## Задача 5: Range Sum Query (Immutable) 
class NumArray
{
    private array $prefix;

    public function __construct(array $nums)
    {
        $this->prefix = array_fill(0, count($nums) + 1, 0);
        for ($i = 0; $i < count($nums); $i++) {
            $this->prefix[$i + 1] = $this->prefix[$i] + $nums[$i];
        }
    }

    public function sumRange(int $left, int $right): int
    {
        return $this->prefix[$right + 1] - $this->prefix[$left];
    }
}

// Usage
$arr = new NumArray([1, 2, 3, 4, 5]);
$arr->sumRange(1, 3);  // 2 + 3 + 4 = 9
$arr->sumRange(0, 4);  // 1 + 2 + 3 + 4 + 5 = 15
## Связь с другими паттернами 
Prefix Sum + HashMap = подсчёт подмассивов с заданным свойством
Prefix Sum + Binary Search = задачи на бинарный поиск по суммам
2D Prefix Sum = быстрые запросы на матрицах
Prefix XOR = задачи на XOR подмассивов

Запомни: Prefix Sum — это предварительная обработка. Потрать O(n) один раз, чтобы отвечать на запросы за O(1). Комбинация Prefix Sum + HashMap позволяет находить подмассивы с заданной суммой за O(n). Для матриц — 2D Prefix Sum с формулой включения-исключения.

Итоги

  1. Prefix Sum позволяет отвечать на запросы суммы подмассива за O(1)
  2. Формула: sum(l, r) = prefix[r+1] - prefix[l]
  3. Prefix Sum + HashMap = подсчёт подмассивов с суммой k за O(n)
  4. 2D Prefix Sum = сумма прямоугольника за O(1) после O(n*m) построения
  5. Трюк с остатками: одинаковый остаток от деления prefix sum = подмассив делится на k

Проверь себя

В задаче Product Except Self зачем нужны два прохода (left и right), если можно просто разделить общее произведение на текущий элемент?

В задаче Subarray Sum Equals K, зачем нужна HashMap с prefix sum, а не просто два вложенных цикла?

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

Для массива [1, 2, 3], k=3. Сколько подмассивов имеют сумму равную 3?

Массив [3, 1, 4, 1, 5]. Чему равен prefix[3]?