Range Addition
Medium · Intervals · Array · Prefix Sum
Problem
You start with an integer array arr of size length, filled with zeros. You are given updates, where updates[i] = [startIdx, endIdx, inc] means: add inc to every element from index startIdx to endIdx, inclusive.
Return arr after applying all the updates.
Aim for O(length + len(updates)) time: mark where each update starts and stops instead of touching every index it covers.
Examples
Input: length = 5, updates = [[0,2,3],[1,4,-1]] Output: [3,2,2,-1,-1]
Indices 0..2 gain 3 and indices 1..4 lose 1: [3, 3-1, 3-1, -1, -1].
Input: length = 3, updates = [[1,1,6],[0,2,1]] Output: [1,7,1]
Index 1 receives 6 and 1; indices 0 and 2 receive only the 1.
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]
Adding the three ranges index by index gives [-2, 0, 3, 5, 3].
Constraints
- 1 <= length <= 10^5
- 0 <= len(updates) <= 10^4
- 0 <= startIdx <= endIdx < length
- -1000 <= inc <= 1000
Approaches
- Sorted edge events — time O(k log k + length), space O(k + length)
Follow-up
If queries for single values were mixed in between the updates, the marks would need a structure that sums a prefix quickly: a Fenwick tree does both a point mark and a prefix sum in O(log n). In two dimensions each update becomes four corner marks and the rebuild is a 2D prefix sum.
Related problems
Start free on Cariara · Coding problems · System design studio
