Suppose we have a static sequence of values a1, a2, ..., an drawn from some group, and want to be able to compute the total value (according to the group operation) of any contiguous subrange. That is, given a range [i, j], we want to compute a value ai + ai+1 + ... + aj. For example, we might have a sequence of integers and want to compute the sum, or perhaps the bitwise xor (but not the maximum) of all the values in any particular subrange.

Of course, we could simply compute a1 + a2 + ... + aj directly, but that takes O(n) time. With some simple preprocessing, it’s possible to compute the value of any range in constant time.

The key idea is to compute the prefix sums of the values in the sequence. Pi = a1 + a2 + ... + ai. Then, the value of any range [i, j] just compute Pj - inv P(i-1) - that is, we start with a prefix that ends at the right place, then cancel or "subtract" the prefix that ends right before the range we want.

From blog by Brent Yorgey Competitive programming in Haskell: prefix sums.

Examples

The prefix sums of the list [1, 2, 3, 4] is [0, 1, 3, 6, 10]:

prefix [Sum 1, Sum 2, Sum 3, Sum 4] = [Sum 0, Sum 1, Sum 3, Sum 6, Sum 10]

The range sum of the elements at indices 1 and 2 is 3:

range (prefix [Sum 1, Sum 2, Sum 3, Sum 4]) 1 2 = Sum 3

Notes on Tests

The Sum monoid is defined by the numerical addition operator and 0 as the neutral element.

For more see Data.Monoid.

Notes on Property Tests

The property-based tests verifies that the range functions correctly calculate sums of subranges for arbitrary lists:

it "works for arbitrary prefix lists (property-based test)" $
  property $ (ys :: [Sum Int])(NonNegative i) (NonNegative j) ->
    let arr      = prefix (map Sum ys)
        n        = length ys
        low      = 1 + i mod max 1 n  -- ensure valid index
        high     = low + j mod max 0 (n - low + 1)
        expected = sum (drop (low - 1) (take high ys))
    in n > 0 ==> range arr low high == Sum expected

Breaking it down:

1. Input generation

• xs :: [Sum Int]: QuickCheck generates random lists of Sum Monoid values
• ys :: [Int]: QuickCheck generates random integer lists
• NonNegative i and NonNegative j: Random non-negative integers

2. Variable setup

• arr = prefix (map Sum ys): @: Converts integers to prefix Sums of Monoid values
• arr = map Sum ys: Converts integers to Sum monoid values
• n = length ys: Gets list length
• low = 1 + i mod max 1 n: Creates a valid starting index (1-indexed)
• high = low + j mod max 0 (n - low + 1): Creates a valid ending index ≥ low

3. Expected result calculation

• expected = sum (drop (low - 1) (take high ys)): Directly calculates the sum by:

  • Taking first high elements
  • Dropping first low-1 elements
  • Summing the remainder

4. Test condition

• n > 0 ==>: Only test non-empty lists
• rangeSum arr low high == Just (Sum expected): Verify function matches direct calculation

This tests that the optimised rangeSum implementation using prefix sums gives the same results as the straightforward direct calculation.