Prefix sums revisited

This station is about questions on a stretch of a list: the total of these values, the smallest of them. Answering each question by reading the stretch costs O(n). With some work done in advance, the answer can cost O(1) or O(log n). The simplest case is a total over a list that never changes, and the tool is one you have met before: prefix sums.

Range questions

A range is a stretch of neighbouring positions of a list. In this station, as in Python’s slices, the range a[l:r] means positions l up to but not including r: it has r − l values. Leaving out the last position is called a half-open range (BSRC). It makes lengths and joins simple: a[l:m] and a[m:r] together are exactly a[l:r].

A range query asks a question about one range, such as its sum or its minimum. The lessons ahead differ in two things: which questions they answer, and whether the list may change between questions.

• Prefix sums (this lesson): sums, list fixed. O(1) per question.
• Sparse table (lesson 2): minimum or maximum, list fixed. O(1) per question.
• Fenwick tree (lesson 3): sums, single values change. O(log n) for both.
• Segment tree (lessons 4 and 5): almost any question, single values or whole ranges change. O(log n).
• Square-root decomposition (lesson 6): a simpler, slower method that bends to odd questions. O(√n).

Prefix sums

ARRS-4 built the list of prefix sums: p[k] is the total of the first k values, a[0] + … + a[k − 1], with p[0] = 0. The total of a range is then the difference of two prefix sums: the first r values, minus the first l.

Building p takes one addition per value, O(n). After that, every range total costs two reads and a subtraction, O(1), whatever the length of the range. HASH-6 used the same identity, turned around, to count ranges with a given total.

The method needs subtraction to undo addition. It works for sums, for XOR (since x ^ x = 0, TRIE-5) and for counts, but not for minimum: knowing the smallest of the first 7 values and of the first 2 says nothing about the smallest of positions 2 to 6. Lesson 2 handles minimum.

Adding to ranges

Now turn the question round. The list changes by many updates of the form “add v to every value in a[l:r]”, and the final list is needed only after all of them. Doing each add with a loop costs O(n).

As in ARRS-4, keep a difference list d of length n + 1, all zeros. For each update, do d[l] += v and d[r] -= v. At the end, the running total of d is the list of changes: a[k] grows by d[0] + … + d[k]. The first change switches the add on at position l, and the second switches it off at r. Step through “Adding to ranges”.

So each update is O(1), and the final pass is O(n). The difference list and the prefix sum undo each other: the differences of the prefix sums give back the list, and the other way round. Practice RNGQ-P1 uses both.

Two dimensions

For a grid, let P[i][j] be the total of the rectangle of the first i rows and first j columns. Any rectangle is then a sum and difference of four corners. Rows r1 to r2 − 1 and columns c1 to c2 − 1 total:

P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]

The two subtractions both remove the top-left corner rectangle, so it is added back once. Building P uses the same rule:

P[i + 1][j + 1] = g[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]

An image filter that averages a box around every pixel uses exactly this (a “summed-area table”).

In Python

from itertools import accumulate

a = [3, 1, 4, 1, 5, 9, 2]
p = [0, *accumulate(a)]      # [0, 3, 4, 8, 9, 14, 23, 25]
p[5] - p[2]                  # 10, the total of a[2:5]

# the difference list, then the running total
d = [0] * (len(a) + 1)
for l, r, v in [(1, 4, 2), (3, 7, 5)]:
    d[l] += v
    d[r] -= v
changes = list(accumulate(d))[:-1]

itertools.accumulate gives running totals, computed in C, so it is faster than a Python loop. [0, *accumulate(a)] puts a 0 in front of them: the * spreads the running totals into the new list.