Префиксные суммы

живой пример

import java.util.Arrays;

public class Revenue {
    private final long[] prefix;

    Revenue(int[] daily) {
        prefix = new long[daily.length + 1];
        for (int i = 0; i < daily.length; i++) prefix[i + 1] = prefix[i] + daily[i];
    }

    long range(int l, int r) {
        return prefix[r + 1] - prefix[l];
    }

    public static void main(String[] args) {
        Revenue revenue = new Revenue(new int[]{2, 5, 1, 4, 3, 7, 2, 6});
        System.out.println("префиксы: " + Arrays.toString(revenue.prefix));
        System.out.println("дни 1..3: " + revenue.range(1, 3));
        System.out.println("дни 4..7: " + revenue.range(4, 7));
    }
}

живой пример

package main

import "fmt"

type Revenue struct{ prefix []int64 }

func NewRevenue(daily []int) *Revenue {
	prefix := make([]int64, len(daily)+1)
	for i, v := range daily {
		prefix[i+1] = prefix[i] + int64(v)
	}
	return &Revenue{prefix}
}

func (r *Revenue) Range(l, h int) int64 { return r.prefix[h+1] - r.prefix[l] }

func main() {
	revenue := NewRevenue([]int{2, 5, 1, 4, 3, 7, 2, 6})
	fmt.Println("префиксы:", revenue.prefix)
	fmt.Println("дни 1..3:", revenue.Range(1, 3))
	fmt.Println("дни 4..7:", revenue.Range(4, 7))
}

живой пример

class Revenue {
  constructor(daily) {
    this.prefix = new Array(daily.length + 1).fill(0);
    for (let i = 0; i < daily.length; i++) this.prefix[i + 1] = this.prefix[i] + daily[i];
  }
  range(l, r) { return this.prefix[r + 1] - this.prefix[l]; }
}

const revenue = new Revenue([2, 5, 1, 4, 3, 7, 2, 6]);
console.log("префиксы:", revenue.prefix);
console.log("дни 1..3:", revenue.range(1, 3));
console.log("дни 4..7:", revenue.range(4, 7));

живой пример

class Revenue:
    def __init__(self, daily: list[int]) -> None:
        self.prefix = [0] * (len(daily) + 1)
        for i, v in enumerate(daily):
            self.prefix[i + 1] = self.prefix[i] + v

    def range(self, l: int, r: int) -> int:
        return self.prefix[r + 1] - self.prefix[l]


revenue = Revenue([2, 5, 1, 4, 3, 7, 2, 6])
print("префиксы:", revenue.prefix)
print("дни 1..3:", revenue.range(1, 3))
print("дни 4..7:", revenue.range(4, 7))

живой пример

import java.util.Arrays;

public class Promotions {
    public static void main(String[] args) {
        int days = 8;
        int[][] ranges = {{0, 2}, {1, 5}, {4, 7}};
        int[] diff = new int[days + 1];
        for (int[] r : ranges) {
            diff[r[0]] += 1;
            diff[r[1] + 1] -= 1;
        }
        int[] result = new int[days];
        int running = 0;
        for (int i = 0; i < days; i++) {
            running += diff[i];
            result[i] = running;
        }
        System.out.println("акций в день: " + Arrays.toString(result));
    }
}

живой пример

package main

import "fmt"

func main() {
	days := 8
	ranges := [][2]int{{0, 2}, {1, 5}, {4, 7}}
	diff := make([]int, days+1)
	for _, r := range ranges {
		diff[r[0]]++
		diff[r[1]+1]--
	}
	result := make([]int, days)
	running := 0
	for i := 0; i < days; i++ {
		running += diff[i]
		result[i] = running
	}
	fmt.Println("акций в день:", result)
}

живой пример

const days = 8;
const ranges = [[0, 2], [1, 5], [4, 7]];
const diff = new Array(days + 1).fill(0);
for (const [from, to] of ranges) {
  diff[from] += 1;
  diff[to + 1] -= 1;
}
const result = [];
let running = 0;
for (let i = 0; i < days; i++) {
  running += diff[i];
  result.push(running);
}
console.log("акций в день:", result);

живой пример

days = 8
ranges = [(0, 2), (1, 5), (4, 7)]
diff = [0] * (days + 1)
for start, end in ranges:
    diff[start] += 1
    diff[end + 1] -= 1
result = []
running = 0
for i in range(days):
    running += diff[i]
    result.append(running)
print("акций в день:", result)

живой пример

public class Prefix2D {
    public static void main(String[] args) {
        int[][] sales = {{2, 5, 1}, {4, 3, 7}, {2, 6, 1}};
        long[][] p = new long[4][4];
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                p[i + 1][j + 1] = sales[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j];
        long rect = p[3][3] - p[1][3] - p[3][1] + p[1][1];
        System.out.println("сумма нижнего правого квадрата 2×2: " + rect);
    }
}

живой пример

package main

import "fmt"

func main() {
	sales := [][]int{{2, 5, 1}, {4, 3, 7}, {2, 6, 1}}
	p := make([][]int64, 4)
	for i := range p {
		p[i] = make([]int64, 4)
	}
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			p[i+1][j+1] = int64(sales[i][j]) + p[i][j+1] + p[i+1][j] - p[i][j]
		}
	}
	rect := p[3][3] - p[1][3] - p[3][1] + p[1][1]
	fmt.Println("сумма нижнего правого квадрата 2×2:", rect)
}

живой пример

const sales = [[2, 5, 1], [4, 3, 7], [2, 6, 1]];
const p = Array.from({ length: 4 }, () => new Array(4).fill(0));
for (let i = 0; i < 3; i++)
  for (let j = 0; j < 3; j++)
    p[i + 1][j + 1] = sales[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j];
const rect = p[3][3] - p[1][3] - p[3][1] + p[1][1];
console.log("сумма нижнего правого квадрата 2×2:", rect);

живой пример

sales = [[2, 5, 1], [4, 3, 7], [2, 6, 1]]
p = [[0] * 4 for _ in range(4)]
for i in range(3):
    for j in range(3):
        p[i + 1][j + 1] = sales[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j]
rect = p[3][3] - p[1][3] - p[3][1] + p[1][1]
print("сумма нижнего правого квадрата 2×2:", rect)

Готовой структуры «сумма на отрезке» в стандартной библиотеке нет — префиксный массив строят сами. Зато есть готовый способ его посчитать и выбор, в чём хранить.

Хранят в примитивном long[], и не из вредности. ArrayList<Long> держит не числа, а ссылки на объекты Long: каждое значение — отдельный объект в куче, памяти уходит в несколько раз больше, а проход по списку прыгает по памяти вместо того, чтобы идти подряд. Формально сложность та же, на деле разница в разы — а нарастающий итог как раз про один длинный последовательный проход.

Сам нарастающий итог библиотека посчитать умеет — это Arrays.parallelPrefix:

живой пример

import java.util.Arrays;

public class ParallelPrefix {
    public static void main(String[] args) {
        long[] daily = {2, 5, 1, 4};
        System.out.println("до вызова: " + Arrays.toString(daily));
        Arrays.parallelPrefix(daily, Long::sum);
        System.out.println("после:     " + Arrays.toString(daily));
    }
}

Вторым аргументом идёт операция — необязательно сложение, но обязательно ассоциативная: метод режет массив на куски и считает их независимо, поэтому от порядка расстановки скобок результат зависеть не должен.

Грабля тут одна, зато обидная, и пример её показывает: метод работает на месте. После вызова исходных чисел у вас больше нет — в массиве лежит только накопленный итог, и дневную выручку уже не восстановить. Нулевого элемента слева он тоже не добавляет, а без него формула требует особого случая для отрезка с нулевой позиции. Массив под префиксы всё равно готовят руками: на единицу длиннее, с нулём в начале и копией данных внутри. И «parallel» в названии — не обещание выигрыша: разбиение работы по потокам окупается на сотнях тысяч элементов, на коротком массиве обычный цикл в одну строку быстрее.

Готовой структуры «сумма на отрезке» в стандартной библиотеке нет — префиксный массив строят сами, и готовой функции для нарастающего итога тоже нет: это цикл в три строки. Зато есть выбор, в чём хранить, и он простой.

Хранят в []int64 или []int, который на 64-битных платформах и есть int64. Упаковки в Go у чисел нет: срез хранит сами значения подряд, проход по нему идёт по памяти последовательно, и это ровно тот случай, где срез раскрывается лучше всего, потому что нарастающий итог — один длинный последовательный проход.

Сам нарастающий итог считают так:

живой пример

package main

import "fmt"

func main() {
	daily := []int64{2, 5, 1, 4}
	prefix := make([]int64, len(daily)+1)
	for i, v := range daily {
		prefix[i+1] = prefix[i] + v
	}
	fmt.Println("данные:  ", daily)
	fmt.Println("префиксы:", prefix)
}

Отдельный срез на единицу длиннее, с нулём в начале — и исходные данные целы. Соблазн сэкономить и накапливать на месте, daily[i] += daily[i-1], кончается тем же, чем в других языках: исходных чисел у вас больше нет, дневную выручку уже не восстановить, а формула для отрезка с нулевой позиции требует особого случая. Параллельного варианта в стандартной библиотеке нет; когда данных сотни миллионов, срез режут на куски по горутинам, считают итоги кусков, а потом сдвигают каждый кусок на сумму предыдущих, это два прохода вместо одного, и окупается такое редко.

Грабля тут одна: переполнение int64 в Go такое же молчаливое, как в Java, число просто переходит через край и становится отрицательным. Для денег в копейках 64 бит хватает с запасом, а вот int32 под суммы не берут никогда.

Готовой структуры «сумма на отрезке» в стандартной библиотеке нет — префиксный массив строят сами. Готовой функции для нарастающего итога тоже нет, но reduce с накоплением в массив пишется в одну строку.

Хранят в обычном массиве чисел: пока в нём лежат только числа, движок V8 держит их плотно, а для больших объёмов есть Float64Array. Упаковки в объекты, как в Java, здесь нет, зато есть другое: число в JavaScript всегда дробное, и целые точны только до 2⁵³, около девяти квадриллионов.

Сам нарастающий итог считают так:

живой пример

const daily = [2, 5, 1, 4];
const prefix = daily.reduce((acc, v) => (acc.push(acc.at(-1) + v), acc), [0]);
console.log("данные:  ", daily);
console.log("префиксы:", prefix);
console.log("2⁵³ + 1 =", 2 ** 53 + 1, "— точность кончилась");

Отдельный массив на единицу длиннее, с нулём в начале — и исходные данные целы. Соблазн накапливать на месте, daily[i] += daily[i - 1], кончается тем же, чем в других языках: исходных чисел у вас больше нет, а формула для отрезка с нулевой позиции требует особого случая. Обычный цикл for здесь быстрее reduce и читается не хуже; reduce берут, когда хочется одной строки.

Грабля тут одна, и она не похожа на переполнение в Java: сумма никогда не станет отрицательной, она потеряет точность. За 2⁵³ соседние целые числа перестают различаться, и 2 ** 53 + 1 печатается как 2 ** 53, без ошибки и без предупреждения. Для денег в копейках это далеко, а для сумм байтов или наносекунд уже нет; тогда берут BigInt и BigInt64Array, где арифметика точная, но заметно медленнее.

Готовой структуры «сумма на отрезке» в стандартной библиотеке нет — префиксный массив строят сами. Зато нарастающий итог библиотека считает сама, и делает это удобнее, чем аналог в Java.

Хранят в обычном list. Число в Python это отдельный объект, и список хранит ссылки на объекты, поэтому проход по нему прыгает по памяти, а не идёт подряд; на миллионах элементов это в разы медленнее, чем в Go, и тогда берут NumPy с np.cumsum, где числа лежат плотно. Но на тысячах и десятках тысяч элементов список справляется.

Сам нарастающий итог считает itertools.accumulate:

живой пример

from itertools import accumulate

daily = [2, 5, 1, 4]
prefix = list(accumulate(daily, initial=0))
print("данные:  ", daily)
print("префиксы:", prefix)

Параметр initial=0 добавляет тот самый нулевой элемент слева, так что формула для отрезка работает без особых случаев, а исходный список остаётся цел: accumulate ленивый и ничего не правит на месте. Вторым аргументом можно передать операцию, необязательно сложение, accumulate(daily, max) даёт нарастающий максимум.

Грабля тут одна, и она обратная к переполнению в Java: целые в Python не переполняются никогда, сумма растёт сколько нужно, и об этом легко забыть, перейдя на NumPy. np.cumsum над массивом int32 молча переходит через край и даёт отрицательную сумму, как Java; для сумм там всегда указывают dtype=np.int64.

class Fenwick {
    private final long[] tree;           // индексы с 1
    Fenwick(int n) { tree = new long[n + 1]; }
    void add(int i, long delta) {        // a[i] += delta
        for (; i < tree.length; i += i & -i) tree[i] += delta;
    }
    long prefix(int i) {                 // сумма a[1..i]
        long s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }
    long range(int l, int r) { return prefix(r) - prefix(l - 1); }
}

type Fenwick struct{ tree []int64 } // индексы с 1

func NewFenwick(n int) *Fenwick { return &Fenwick{make([]int64, n+1)} }

func (f *Fenwick) Add(i int, delta int64) { // a[i] += delta
	for ; i < len(f.tree); i += i & -i {
		f.tree[i] += delta
	}
}

func (f *Fenwick) Prefix(i int) int64 { // сумма a[1..i]
	var s int64
	for ; i > 0; i -= i & -i {
		s += f.tree[i]
	}
	return s
}

func (f *Fenwick) Range(l, r int) int64 { return f.Prefix(r) - f.Prefix(l-1) }

class Fenwick {
  constructor(n) { this.tree = new Array(n + 1).fill(0); }   // индексы с 1
  add(i, delta) {                                             // a[i] += delta
    for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
  }
  prefix(i) {                                                 // сумма a[1..i]
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.tree[i];
    return s;
  }
  range(l, r) { return this.prefix(r) - this.prefix(l - 1); }
}

class Fenwick:
    def __init__(self, n: int) -> None:
        self.tree = [0] * (n + 1)          # индексы с 1

    def add(self, i: int, delta: int) -> None:      # a[i] += delta
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i: int) -> int:                # сумма a[1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range(self, l: int, r: int) -> int:
        return self.prefix(r) - self.prefix(l - 1)