Difference Array Technique
The difference array technique (also called prefix sum of differences) is an efficient method for handling multiple range updates on arrays.
Core Concept
Instead of storing actual values, we store differences between consecutive elements. This allows range updates in O(1) time by modifying only two positions.
function differenceArray(arr) {
const diff = new Array(arr.length + 1).fill(0);
diff[0] = arr[0];
for(let i = 1; i < arr.length; i++) {
diff[i] = arr[i] - arr[i-1];
}
return diff;
}
function rangeUpdate(arr, updates) {
const n = arr.length;
const diff = differenceArray(arr);
updates.forEach(([start, end, value]) => {
diff[start] += value;
if(end + 1 < n) diff[end + 1] -= value;
});
const result = new Array(n);
result[0] = diff[0];
for(let i = 1; i < n; i++) {
result[i] = result[i-1] + diff[i];
}
return result;
}
370. Range Addition
/**
* @param {number} length
* @param {number[][]} updates
* @return {number[]}
*/
function getModifiedArray(length, updates) {
const res = Array(length).fill(0)
updates.forEach(([s, e, v]) => {
res[s] += v
if (e + 1 < length) res[e + 1] -= v
})
for (let i = 1; i < length; i++) {
res[i] += res[i - 1]
}
return res
};
Time Complexity
- Create difference array: O(n)
- Range update: O(1)
- Reconstruct array: O(n)
When to Use
- Multiple range updates required
- Need final array state
- Want to avoid updating each element in range