Data Structures19 sections · 729 units
Open in Course

Difference Array Visualization

Trace an example

Array: [0,0,0,0,0][0, 0, 0, 0, 0]. You want to add 33 to indices 11 through 33. Difference array starts as: [0,0,0,0,0][0, 0, 0, 0, 0].

Update: diff[1]+=3diff[1] += 3, diff[4]−=3diff[4] -= 3.

Now diff=[0,3,0,0,−3]diff = [0, 3, 0, 0, -3].

Take prefix sum of diffdiff: [0,0+3,0+3+0,0+3+0+0,0+3+0+0−3]=[0,3,3,3,0][0, 0+3, 0+3+0, 0+3+0+0, 0+3+0+0-3] = [0, 3, 3, 3, 0].

Elements at indices 1,2,31, 2, 3 increased by 33. The rest stayed at 00.