← Back to Games

Range Builder

Apply range updates using difference array technique!

⚡ Apply Range Update

Difference Array
Final Array (Prefix Sum of Diff)

📝 Applied Updates

No updates applied yet...

📐 Difference Array Technique

// Instead of updating arr[L..R] directly (O(n) each)
// We use difference array (O(1) per update)

function rangeUpdate(diff, L, R, val):
  diff[L] += val      // Start of effect
  diff[R+1] -= val    // End of effect + 1

function getFinal(diff):
  // Prefix sum gives final array
  for i = 1 to n-1:
    diff[i] += diff[i-1]