Cast range-update spells using the Difference Array technique!
Instead of updating every element in a range (O(n) per update), we use a difference array:
val at index Lval at index R+1At the end, compute prefix sum of difference array to get the final result!
No spells cast yet. Cast your first spell!
The difference array trick converts O(n) range updates into O(1) operations!
Traditional approach: M updates × N array size = O(M×N)
Difference array: M updates (O(1) each) + 1 prefix sum = O(M + N)