DEV Community

Jayaprasanna Roddam
Jayaprasanna Roddam

Posted on

Difference Array

#programming #tutorial #python #datastructures

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)