Lv.1arraydifference-arrayprefix-sum
Range Add Updates
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
n members (numbered 0 to n - 1) all start with a balance of 0. Each update [l, r, v] adds v to the balance of every
member from l to r inclusive (v may be negative). Apply all updates and return the final balances in member order.
Examples
| n | updates | result |
|---|---|---|
5 | [[1, 3, 2], [2, 4, 3], [0, 2, -2]] | [-2, 0, 3, 5, 3] |
3 | [[0, 2, 1000000000], [0, 2, 1000000000], [0, 2, 1000000000]] | [3000000000, 3000000000, 3000000000] |
1 | [[0, 0, -7]] | [-7] |
Balances can exceed the 32-bit range.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, updates: int[][]) → long[]
Constraints
-
n -
updates.length updates[i] = [l, r, v],n,- Final balances fit in a 64-bit integer (
long).
Expected complexity
- Time
- O(N + Q)
- Space
- O(N)
Examples
| n | updates | Expected |
|---|---|---|
5 | [[1,3,2],[2,4,3],[0,2,-2]] | [-2,0,3,5,3] |
3 | [[0,2,1000000000],[0,2,1000000000],[0,2,1000000000]] | [3000000000,3000000000,3000000000] |
1 | [[0,0,-7]] | [-7] |
Hint
Hint
Instead of adding v to every position, mark where it starts and stops: diff[l] += v, diff[r + 1] -= v. A running sum of
diff then gives every final balance (keep it in 64 bits). Updating every position of every range is and exceeds
the time limit; the difference array is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 284 ms | estimated |
| C++ (GCC, gnu++23) | 284 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 2014 ms | derived |
| Kotlin 2.4 (JVM) | 1568 ms | estimated |
| C# 14 (.NET 10) | 1568 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |