Difference Array Technique

Understanding Difference Arrays

Imagine you have a problem. You have a list of numbers. This list is very big. You are given many tasks to update this list.

The task is to add a number to a range of indexes. For example, the first task could be to add 5 to all numbers from index 2 to index 7. If you do this one by one for every number on every task, it will be very slow. Your code will not run fast enough.

We need a faster way. This is where the Difference Array technique helps.

The Problem

Let's start with a simple example. We have an array of size 6 initialized with 0.

A = [0, 0, 0, 0, 0, 0]

We have two updates to do.

1. Add 2 to the numbers from index 1 to 3.
2. Add 4 to the numbers from index 3 to 4.

All indexing in this post is 0-based.

Solution 1: Brute Force

This is the obvious way to do it. We just go through the given updates one by one and add the numbers to the array. We literally do what's being said.

First, we apply update 1. Add 2 from index 1 to 3.
A = [0, 2, 2, 2, 0, 0]

Next, we apply update 2. Add 4 from index 3 to 4.
The value at index 3 is 2. So 2 + 4 becomes 6.
The value at index 4 is 0. So 0 + 4 becomes 4.

The final array is:
A = [0, 2, 2, 6, 4, 0]

This works. But if the array is huge and the given number of updates is huge, this takes too much time.

Solution 2: The Difference Array

Let us try a smarter way. Instead of adding the number to every index, we only mark the start and the end.

Here, we plan to take advantage of the prefix sum.

We create a new array D the same size as A, initially filled with zeros.
D = [0, 0, 0, 0, 0, 0]

Now, for each update, we have to add a value x from index L to index R. What we actually do in this case is simple:

1. At index L, we add the value x.
2. At index R + 1, we subtract the value x.

If R + 1 is outside the array bounds, then we simply don't do anything.

Let us try the same updates.

Update 1: Add 2 from index 1 to 3.
L = 1, R = 3, x = 2.
Add 2 at index 1. Subtract 2 at index 4 (which is 3 + 1).
D = [0, 2, 0, 0, -2, 0]

Update 2: Add 4 from index 3 to 4.
L = 3, R = 4, x = 4.
Add 4 at index 3. Subtract 4 at index 5 (R+1).
D = [0, 2, 0, 4, -2, -4]

Now we have processed all updates very fast. But this array D looks weird. It is not the answer. To get the answer, we take the prefix sum of this array.

Prefix sum means we keep adding the numbers as we go from left to right.

• Index 0: 0
• Index 1: 2 + 0 = 2
• Index 2: 0 + 2 = 2
• Index 3: 4 + 2 = 6
• Index 4: -2 + 6 = 4
• Index 5: -4 + 4 = 0

The result is [0, 2, 2, 6, 4, 0]. This matches our brute force answer exactly. It works perfectly for arrays starting with 0.

But what if the array was not initialized with 0?

The Problem with Non-Zero Arrays

Now, let us change the problem. What if the array was not 0 at the start? What if it was initialized with 1?

A = [1, 1, 1, 1, 1, 1]

We do the same updates:

1. Add 2 to the range [1, 3]
2. Add 4 to the range [3, 4]

This is where the magic happens! To handle an array that doesn't start with zeros, we just need to build our difference array D differently.

Instead of D being all zeros, we build D so that its prefix sum gives us our starting array A.

Here's the rule:

1. D[0] is just A[0].
2. For every other index i, D[i] = A[i] - A[i-1].

Let's build D for our A = [1, 1, 1, 1, 1, 1]:

• D[0] = A[0] = 1
• D[1] = A[1] - A[0] = 1 - 1 = 0
• D[2] = A[2] - A[1] = 1 - 1 = 0
• D[3] = A[3] - A[2] = 1 - 1 = 0
• D[4] = A[4] - A[3] = 1 - 1 = 0
• D[5] = A[5] - A[4] = 1 - 1 = 0

So, our starting D array is D = [1, 0, 0, 0, 0, 0].
(If you take the prefix sum of this, you get [1, 1, 1, 1, 1, 1], which is our original A. Perfect!)

Now, we apply the updates to this array D, just like we did before.

Initially: D = [1, 0, 0, 0, 0, 0]

Update 1: Add 2 from index 1 to 3.
L = 1, R = 3, x = 2.
Add 2 at index 1. Subtract 2 at index 4 (which is 3 + 1). Then we get D = [1, 2, 0, 0, -2, 0]

Update 2: Add 4 from index 3 to 4.
L = 3, R = 4, x = 4.
Add 4 at index 3. Subtract 4 at index 5 (R+1). Then we get D = [1, 2, 0, 4, -2, -4]

We've processed all updates. Now for the final step: take the prefix sum of this D to get our final answer.

• Index 0: 1
• Index 1: 2 + 1 = 3
• Index 2: 0 + 3 = 3
• Index 3: 4 + 3 = 7
• Index 4: -2 + 7 = 5
• Index 5: -4 + 5 = 1

The final array is [1, 3, 3, 7, 5, 1].

Let's check this against our Expected Answer: [1, 3, 3, 7, 5, 1].
It's a perfect match!

So, the trick works for any starting array. You just have to build the initial difference array D correctly from your starting array A first, and then apply all your updates to D.

Try the same algorithm with the following example and see for yourself.
A = [2,1,4,5,1,2,3,9,8,2]

We do these updates:

1. Add 1 to the range [3, 6]
2. Add 4 to the range [4, 8]
3. Add 2 to the range [0, 3]

Answer:
[3,2,5,7,6,7,8,13,12,2]