Difference Array
The inverse trick of Prefix Sum: instead of computing range sums fast, it applies range UPDATES fast. Each update touches only 2 array cells; recovering the final array is one prefix-sum pass.
- Category
- Algorithmic Techniques
- Time complexity
- O(1) update, O(n) build
- Space complexity
- O(n)
Pseudocode
diff[s] += delta; diff[e+1] -= delta (per update) final[i] = prefix-sum of diff up to i
Reference implementation
diff = [0] * (n+1)
def add_range(s, e, delta):
diff[s] += delta; diff[e+1] -= delta
# after all updates:
running = 0; result = []
for d in diff[:n]:
running += d; result.append(running)