Funcia
Lv.1arraydifference-arrayprefix-sum

Range Add Updates

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

nupdatesresult
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

  • 1≤1 \le n ≤200,000\le 200{,}000
  • 1≤1 \le updates.length ≤200,000\le 200{,}000
  • updates[i] = [l, r, v], 0≤l≤r<0 \le l \le r < n, −109≤v≤109-10^9 \le v \le 10^9
  • Final balances fit in a 64-bit integer (long).

Expected complexity

Time
O(N + Q)
Space
O(N)

Examples

nupdatesExpected
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 O(N×Q)O(N \times Q) and exceeds the time limit; the difference array is O(N+Q)O(N + Q).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)284 msestimated
C++ (GCC, gnu++23)284 msderived
Python 3.131000 msderived
Java 252014 msderived
Kotlin 2.4 (JVM)1568 msestimated
C# 14 (.NET 10)1568 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.