PrefixPrefix Techniques

Difference Array

Apply many range increments in O(1) each by writing +v at l and −v at r+1, then recover the final array with a single prefix-sum pass.

Learn Difference Array →
a
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
D (differences)
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
1/13Apply 3 range increments to the array. Doing each in O(r−l) would be slow, so record only the endpoints in a difference array D of size n+1.
Range being updatedD entry touchedPrefix stepRecovered value
PseudocodeLearn Difference Array →
1D = [0] * (n + 1)
2for each update (l, r, v):
3  D[l] += v; D[r+1] -= v
4a[0] = D[0]; for i in 1..n-1: a[i] = a[i-1] + D[i]
Variables
n8
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(n)
Speed