Skip to main content

Префиксная сумма

Префиксная сумма (Prefix sum) — это техника, которая может быть использована для работы с массивами (чисел).
Идея заключается в создании массива prefix, где prefix[i] представляет собой сумму всех элементов от начала массива до индекса i (включительно).
Например, для заданного массива nums = [5, 2, 1, 6, 3, 8], массив префиксных сумм будет выглядеть так: prefix = [5, 7, 8, 14, 17, 25].

Когда подмассив начинается с индекса 0, он считается "префиксом" массива.
Префиксная сумма представляет собой сумму всех префиксов.

Префиксные суммы позволяют находить сумму любого подмассива за 𝑂(1).
Если мы хотим найти сумму подмассива от i до j (включительно), то ответ будет prefix[j] - prefix[i - 1], или prefix[j] - prefix[i] + nums[i], если вы не хотите иметь дело с выходом за границы массива, когда i = 0. Это работает потому, что prefix[i - 1] является суммой всех элементов перед индексом i. Когда вы вычитаете эту сумму из суммы всех элементов до индекса j, вы получаете сумму всех элементов, начиная с индекса i и заканчивая индексом j, что и является искомой суммой.

Псевдокод​

prefix = [nums[0]]
for (int i = 1; i < nums.length; i++)
    prefix.append(nums[i] + prefix[prefix.length - 1])

Изначально мы начинаем только с первого элемента. Затем мы итерируемся, начиная с индекса 1. В любой момент последний элемент prefix будет представлять собой сумму всех элементов входного массива до, но не включая, индекс i. Таким образом, мы можем добавить это значение плюс текущее значение в конец prefix и продолжить к следующему элементу.

Префиксная сумма — отличный инструмент, когда задача включает суммы подмассива. Построение префиксной суммы стоит 𝑂(𝑛), но позволяет выполнять все последующие запросы подмассива за 𝑂(1), что обычно может улучшить временную сложность алгоритма на фактор 𝑂(𝑛), где 𝑛 — длина массива. Давайте рассмотрим несколько примеров.

Построение префиксной суммы — это форма предварительной обработки.
Предварительная обработка — это полезная стратегия в различных задачах, где мы храним предварительно вычисленные данные в структуре данных перед запуском основной логики нашего алгоритма. Хотя на предварительную обработку требуется время, это вложение, которое сэкономит нам огромное количество времени во время выполнения основных частей алгоритма.

Пример​

Given an integer array nums, an array queries where queries[i] = [x, y] and an integer limit, return a boolean array that represents the answer to each query. A query is true if the sum of the subarray from x to y is less than limit, or false otherwise.

For example, given nums = [1, 6, 3, 2, 7, 2], queries = [[0, 3], [2, 5], [2, 4]], and limit = 13, the answer is [true, false, true]. For each query, the subarray sums are [12, 14, 12].

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @param {number} limit
 * @return {boolean[]}
 */
var answerQueries = function (nums, queries, limit) {
  let prefix = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    prefix.push(nums[i] + prefix[prefix.length - 1]);
  }

  let ans = [];
  for (const [x, y] of queries) {
    let curr = prefix[y] - prefix[x] + nums[x];
    ans.push(curr < limit);
  }

  return ans;
};

Без префиксной суммы ответ на каждый запрос будет 𝑂(𝑛) в худшем случае, где 𝑛 — длина массива nums.
Если m = queries.length, то временная сложность будет 𝑂(𝑛∗𝑚). С префиксной суммой это стоит 𝑂(𝑛) для построения, но затем ответ на каждый запрос будет 𝑂(1). Это дает намного лучшую временную сложность 𝑂(𝑛+𝑚). Мы используем 𝑂(𝑛) пространства для построения префиксной суммы.

Пример: https://leetcode.com/problems/number-of-ways-to-split-array/description/

Дополнение к примеру

Нужен ли нам массив?
В этой задаче порядок, в котором нам нужно обращаться к префиксной сумме, является инкрементальным: чтобы найти leftSection, мы используем prefix[i], где i увеличивается на 1 в каждой итерации.

Таким образом, для вычисления leftSection нам на самом деле не нужен массив. Мы можем просто инициализировать leftSection = 0 и затем вычислять его на лету, добавляя к нему текущий элемент на каждой итерации.

А что насчет rightSection? По определению, правая секция содержит все числа в массиве, которые не входят в левую секцию. Следовательно, мы можем предварительно вычислить сумму всего входного массива как total, а затем вычислять rightSection как total - leftSection.

Мы по-прежнему используем концепцию префиксной суммы, так как каждое значение leftSection представляет собой сумму префикса. Мы просто воспроизвели функциональность, используя целое число вместо массива.


/\*\*

- @param {number[]} nums

- @return {number}
\*/
var waysToSplitArray = function(nums) {
let ans = 0, leftSection = 0, total = 0;
for (const num of nums) {
total += num;
}

    for (let i = 0; i < nums.length - 1; i++) {
        leftSection += nums[i];
        let rightSection = total - leftSection;
        if (leftSection >= rightSection) {
            ans++;
        }
    }

    return ans;

};

Задачи​