Префиксные суммы: что это такое и как используются

Префиксные суммы – это техника, которая помогает эффективно решать задачи, связанные с вычислением суммы элементов подмассива в массиве. Она заключается в том, что заранее вычисляется сумма первых i элементов массива, которую мы сохраняем в специальном массиве, называемом массивом префиксных сумм. Например, предположим, что у нас есть массив a = [1, 2, 3, 4, 5], тогда массив префиксных сумм p будет выглядеть так: p = [1, 3, 6, 10, 15].

Такой подход позволяет эффективно вычислять суммы элементов подмассива. Например, чтобы вычислить сумму элементов на отрезке [2, 4] массива a, мы можем просто вычислить разность p[4] - p[1], то есть 10 - 3 = 7. Это значительно быстрее, чем вычислять сумму элементов массива на каждом шаге.

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

Рассмотрим пример кода, который демонстрирует применение префиксных сумм для вычисления суммы элементов на отрезке массива:

import java.util.*;
public class Main {
  public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5};
    int n = a.length;
    int[] p = new int[n];
    p[0] = a[0];
    for (int i = 1; i < n; i++) {
      p[i] = p[i - 1] + a[i];
    }
    // вычисление суммы элементов на отрезке [2, 4]
    int l = 2, r = 4;
    int sum = p[r] - (l > 0 ? p[l - 1] : 0);
    System.out.println(sum); // выводит "12"
  }
}

Здесь мы вычисляем массив префиксных сумм p, проходя по элементам массива a и суммируя их с предыдущими элементами массива p. Затем мы вычисляем сумму элементов на отрезке [2, 4] массива a, используя значения элементов массива префиксных сумм p.