Difference arrays in Python lists

Why this matters

Suppose you run a shop with a row of 1000 shelves. Each day, a supplier delivers boxes to a range of shelves, from shelf 200 to shelf 450, and you add 3 to the count on each shelf in that range. Next day, another delivery covers shelves 400 to 800. You might receive 50,000 deliveries in a year. If you update each shelf one by one for each delivery, a single delivery can touch up to 1000 shelves, and the total work grows fast.

A difference array solves this kind of problem. You store the changes at only two positions per delivery, the start and the position just after the end. Each delivery then costs a fixed, small amount of work, no matter how many shelves it covers. When all deliveries are recorded, one pass over the list gives the final count on every shelf.

This lesson uses only loops over lists of numbers. It builds on the list indexing shown in the earlier lessons of this module. The rotation lesson before it changes a list in place, and this lesson changes a different, second list that records the changes. The two lessons do not depend on each other.

Plain words first: what a range addition is

A range addition adds the same number to every position from a left index to a right index. Both ends are included. Positions are numbered from 0, so a list of length 8 has positions 0 to 7.

Take a list of 8 zeros:

position:   0  1  2  3  4  5  6  7
value:      0  0  0  0  0  0  0  0

Add 3 to the range from position 1 to position 4. The positions 1, 2, 3 and 4 each gain 3:

position:   0  1  2  3  4  5  6  7
value:      0  3  3  3  3  0  0  0

The simplest program does this with a loop. It goes from the left index to the right index and adds the number to each position. If the range is long, the loop runs many times. If you have many ranges, the total work adds up quickly.

Output:

[0, 3, 3, 3, 3, 0, 0, 0]

The loop for i in range(1, 5) runs four times, once for each position in the range. The end value 5 is not included in range, so the loop stops at 4. A range of 1000 positions would run the loop 1000 times for one update. That cost is what the difference array removes.

The idea: record the edges, not the middle

Here is the key observation. The range addition changes the list only at two places. At the left end, the value jumps up by 3. At the position just after the right end, the value drops back down by 3. Everywhere in between, the value stays the same as the value before it, plus the jump.

A difference array stores these jumps. For a list of values, the difference at position i is the value at i minus the value at the position before it. The first position has no position before it, so its difference is just the value itself. For example:

values:      3  5  5  2
difference:  3  2  0 -3

The first difference is 3, because the start counts as 0. The second is 5 minus 3, which is 2. The third is 5 minus 5, which is 0. The fourth is 2 minus 5, which is -3.

Now look at what a range addition does to the difference array. Adding 3 to the range from 1 to 4 on the list of zeros changes only two differences:

• The difference at position 1 goes up by 3, because the value jumped up at position 1.
• The difference at position 5 goes down by 3, because the value drops back at position 5, the position just after the right end.

No other difference changes. So a range addition becomes two single-position changes, no matter how long the range is.

Adding a range in constant time

Call the difference list diff. It is one position longer than the list of values, so that the position just after the last value fits. Adding value to the range from left to right is two lines:

diff[left] += value
diff[right + 1] -= value

Each line changes one position. The cost is the same whether the range has 1 position or 1000. This is what programmers mean by O(1) time per update. The letter O is the notation that describes how the work grows with the size of the input, and O(1) means the work does not grow.

Look at the first example from the start of the lesson with this rule. Add 3 to the range 1 to 4 on a list of length 8. The left end is 1, so diff[1] += 3. The right end is 4, so the position just after it is 5, and diff[5] -= 3. The diff list is now [0, 3, 0, 0, 0, -3, 0, 0, 0]. Position 0 is not touched.

To keep the two lines in one place, wrap them in a function. The function below is used by every example in the rest of this lesson.

def add_range(diff, left, right, value):
    diff[left] += value
    diff[right + 1] -= value

Recovering the values with one prefix pass

The values are not stored in the difference list. To get them back, you add up the differences from left to right. The running total at each position is the value at that position. This running total is called a prefix sum.

Here is the pass applied to [0, 3, 0, 0, 0, -3, 0, 0, 0]:

position:   0   1   2   3   4   5    6   7
diff:       0   3   0   0   0  -3    0   0
running:    0   3   3   3   3   0    0   0

The running total is 0 at position 0. At position 1, the total is 0 plus 3, which is 3. At position 2, it is still 3, because the difference there is 0. At position 5, the difference is -3, so the total drops back to 0. The final row matches the list of values we wanted.

The pass takes one loop over the list, so it costs O(n) time for n positions. You run it once after all updates are recorded, not after each one. That single pass recovers every value, however many updates there were.

Python has a function that does this pass for you. itertools.accumulate returns the running totals of a list. The loop version shows the rule, and accumulate is what you will see in real code.

Output:

Difference array: [-1, 3, 0, 3, 0, -3, 0, 0, -2]
Final values:     [-1, 2, 2, 5, 5, 2, 2, 2]
With accumulate:  [-1, 2, 2, 5, 5, 2, 2, 2]

The accumulate line runs the pass over all n + 1 positions and then keeps the first n. The extra last position is never read by the recovery, as the next sections show.

Check a few values by hand. Position 0 gets -1 from the update that covers 0 to 2, so its running total is -1. Position 1 gets 3 from the update that covers 1 to 4 and -1 from the update that covers 0 to 2, so 2. Position 3 gets 3 from the update that covers 1 to 4 and 2 from the update that covers 3 to 7, which makes 5. The values show what each update did, and the running total gives the same answer.

Worked example: people in a room

Many questions have this shape. A meeting room is used at several times, and each booking covers a range of minutes. The question is how many people are in the room at each minute. Here each booking adds 1 to a range of minutes. The bookings are shown as pairs of start minute and end minute, with both ends included.

Use the bookings [0, 2], [1, 4], [3, 3] and [5, 7] on minutes 0 to 7. The difference list, with one extra position, gives the answer after one pass.

Output:

People per minute: [1, 2, 2, 2, 1, 1, 1, 1]

Minute 0 has one person, from the first booking. Minute 1 has two, because the first and second bookings both cover it. Minute 3 has two, from the second and third bookings. Minute 4 has one again, because the third booking ended at minute 3. The four bookings were recorded with eight changes in total, and the answer for all eight minutes came from one loop.

Worked example: starting from a non-zero list

Often the values do not start at zero. A shop might already hold 10 items on each shelf, and the updates add or remove items from ranges. The difference list records only the changes. You add the starting values to the recovered changes at the end.

Start with [10, 10, 10, 10, 10]. Add 1 to the range from 0 to 4, and subtract 4 from the range from 2 to 3. The changes are [1, 1, -3, -3, 1], and the final values are the starting values plus the changes.

Output:

base [10, 10, 10, 10, 10] final [11, 11, 7, 7, 11]

Position 2 has the value 7. It received +1 from the first update and -4 from the second, so its change is -3, and 10 minus 3 is 7. Keep the starting list separate from the difference list. Mixing the two is a common mistake, covered below.

Why the extra position at the end

The difference list is one position longer than the values. This is not a waste. Every range ends at some position right, and the update writes to right + 1. When the range reaches the last value, right + 1 equals the length of the values. Without an extra position, that write would be outside the list.

Here is the failure. The list of values has length 5, so its positions are 0 to 4. The program below uses a diff list of length 5, not 6, and adds 9 to the range from 2 to 4. Save it as main.py and run it.

def add_range(diff, left, right, value):
    diff[left] += value
    diff[right + 1] -= value
 
diff = [0] * 5
add_range(diff, 2, 4, 9)

Traceback (most recent call last):
  File "main.py", line 6, in <module>
    add_range(diff, 2, 4, 9)
    ~~~~~~~~~^^^^^^^^^^^^^^^
  File "main.py", line 3, in add_range
    diff[right + 1] -= value
    ~~~~^^^^^^^^^^^
IndexError: list index out of range

The last frame shows the failing line, diff[right + 1] -= value, where right + 1 is 5. The list's last index is 4. The fix is to allocate n + 1 positions for the difference list, as the examples above do. The extra position is never read by the recovery pass, because the pass only goes up to position n minus 1. Its job is to hold the change that stops the range.

Common mistakes

Writing the end change at the right end instead of after it. Some programmers write diff[right] -= value. That removes the increase one position too early. Take the example of adding 1 to the range 0 to 2 on a list of length 4. The correct update is diff[0] += 1 and diff[3] -= 1, which gives the values [1, 1, 1, 0]. The wrong update diff[2] -= 1 gives [1, 1, 0, 0]. Position 2 is 0 when it should be 1. The program does not crash, so this kind of error is hard to see. Check each update by writing out the expected values for a small case.

Output:

correct [1, 1, 1, 0]
wrong [1, 1, 0, 0]

Forgetting the prefix pass. The difference list holds changes, not values. If you print the difference list and call it the answer, you get numbers such as [-1, 3, 0, 3, 0, -3, 0, 0, -2]. The final values need the running total. Always run the recovery loop before you read the results.

Running the prefix pass after every update. The point of the method is to pay for one pass at the end. Running the pass after each update brings back the slow work, because each pass costs O(n). Record all the updates first, then recover once.

Making the difference list the same length as the values. As shown above, a range that ends at the last position needs one more slot. Use n + 1.

Adding the starting values to the difference list. If the starting values are not zero, add them after the recovery pass, as in the shelf example. If you put the starting values into the difference list, the running total adds them up from left to right, so every later value is wrong.

Mixing up the two ends of a booking. A booking that covers minute 3 to minute 5 has its right end at 5, so the update writes to position 6. Some programmers treat the right end as exclusive, meaning it is not counted, and write to 5. That is correct only when the question says that the end is not included. Decide what the right end means before you write the code, and check the convention against a small example.

Practice

Exercise 1. A list of length 6 starts at zeros. Apply these range additions: add 5 to the range 0 to 3, add 2 to the range 2 to 5, and subtract 1 from the range 4 to 4. Find the final values by hand, using the difference list and one prefix pass. Then check the result with the code.

Show the answer

The updates write diff[0] += 5 and diff[4] -= 5, then diff[2] += 2 and diff[6] -= 2, then diff[4] -= 1 and diff[5] += 1. The diff list is [5, 0, 2, 0, -6, 1, -2]. The running totals are 5, 5, 7, 7, 1 and 2. The final values are [5, 5, 7, 7, 1, 2].

Exercise 2. A student writes the update for a range from left to right as diff[left] += value and diff[right] -= value. Predict what goes wrong when the range is 0 to 2 with a value of 1 on a list of length 4. Write the final values the student gets, and the values that are correct.

Show the answer

The student's diff list is [1, 0, -1, 0]. The running totals are 1, 1, 0, 0. The correct values are 1, 1, 1, 0. Position 2 is inside the range, so it should keep the value 1, but the student's update removed it one position too early.

Exercise 3. Starting from the list [7, 7, 7, 7], add 2 to the range 1 to 3. Then subtract 7 from the range 0 to 0. Write the final values. Explain why the diff list needs length 5 when there are 4 values.

Show the answer

The first update changes diff[1] by 2 and diff[4] by -2, which needs position 4. The second update changes diff[0] by -7 and diff[1] by 7. The changes are [-7, 9, 0, 0, -2], and the running totals are -7, 2, 2, 2. Adding the starting value 7 to each running total gives the final values 0, 9, 9, 9. The length is 5 because the range 1 to 3 ends at the last value, and its right end writes to position 4, which is one past the last value.

Exercise 4. Write a function apply_all(n, updates) that takes the length and a list of updates. Each update is a tuple (a fixed group of values in parentheses) of three numbers: left, right and value. The function returns the final values. Test it with the updates (0, 2, 1), (1, 4, 1), (3, 3, 1) and (5, 7, 1) on length 8, and print the result.

Show the answer

Output:

[1, 2, 2, 2, 1, 1, 1, 1]

The function creates the diff list with n + 1 positions, then loops over the updates. Each update runs the two lines of add_range. After the loop it runs the prefix pass for n positions and returns the result. The output is the same as the people-in-a-room example. The line for left, right, value in updates: unpacks each tuple into three names, which saves writing update[0] and so on.

Exercise 5. The list of values has length 5 and the code uses a diff list of length 5 with no extra slot. An update adds 4 to the range 1 to 4. Predict the error message and say which line causes it.

Show the answer

The update writes diff[5] -= 4, because the right end is 4 and the position after it is 5. The diff list has indexes 0 to 4, so Python reports IndexError: list index out of range. The line that causes it is the one that subtracts from diff[right + 1]. The fix is to allocate a diff list of length 6.

Summary

• A range addition adds one value to every position from a left index to a right index, with both ends included.
• A difference list stores the changes at the edges. To add value over left to right, add to diff[left] and subtract from diff[right + 1].
• Each update costs a fixed amount of work, however long the range is.
• After all updates, one running-total pass over the difference list gives the final values. itertools.accumulate does that pass.
• Allocate one extra position, so that a range ending at the last value has a slot for its end change.