Difference Array

OVERVIEW

Difference Array is an optimization technique used to efficiently perform

multiple range update operations on an array.

Instead of updating every element in a range [L, R], we update only the

boundaries and reconstruct the final array later using prefix sums.

This reduces range updates from O(N) to O(1).

WHEN TO USE

Use Difference Array when:

• There are many range update operations


• Final array is needed after all updates


• Updates are additive (increment/decrement)


• Queries are fewer or done after all updates

TIME & SPACE

Update Time per Query : O(1)

Reconstruction Time : O(N)

Space Complexity : O(N)

CORE IDEA

Given an array arr of size N, create a difference array diff of size N.

Definition:

diff[0] = arr[0]

diff[i] = arr[i] - arr[i - 1]

To add value x to range [L, R]:

diff[L] += x

diff[R + 1] -= x (if R + 1 < N)

Final array is obtained by prefix sum of diff.

EXAMPLE 1: Build Difference Array from Original Array

def build_difference_array(arr):

diff = [0] * len(arr)

diff[0] = arr[0]

for i in range(1, len(arr)):

    diff[i] = arr[i] - arr[i - 1]



return diff

EXAMPLE 2: Apply Range Updates Using Difference Array

Problem:

Given an array of size N, apply multiple updates of the form:

add value x to all elements from index L to R (inclusive).

def apply_range_updates(n, updates):

diff = [0] * n

for left, right, value in updates:

    diff[left] += value

    if right + 1 < n:

        diff[right + 1] -= value



return diff

EXAMPLE 3: Reconstruct Final Array from Difference Array

def reconstruct_array(diff):

arr = [0] * len(diff)

arr[0] = diff[0]

for i in range(1, len(diff)):

    arr[i] = arr[i - 1] + diff[i]



return arr

EXAMPLE 4: Full Flow Example

Problem:

Initial array of zeros, apply range updates, get final array.

def range_update_final_array(n, updates):

diff = apply_range_updates(n, updates)

return reconstruct_array(diff)

IDENTIFICATION CHECKLIST

Ask these questions:

• Are there many range update operations?


• Is each update additive?


• Do I need the final array only after all updates?


• Can prefix sums reconstruct the result?

If yes, Difference Array is the ideal technique.

COMMON PITFALLS

• Forgetting to subtract at R + 1


• Out-of-bounds access for R + 1


• Trying to query intermediate states


• Confusing difference array with prefix sum array

SUMMARY

• Convert range updates into boundary updates


• Apply prefix sum to reconstruct array


• Massive optimization for range update problems


• Foundational for advanced techniques like Imos method