Lv.3fenwick-treelazy-propagationsegment-tree
Range Add, Range Sum
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are given an integer array values and a list of commands ops, processed in order:
[1, l, r, x]: addxto every one ofvalues[l],values[l+1], …,values[r].[2, l, r]: reportvalues[l] + values[l+1] + … + values[r].
Return the answers of the 2 commands in the order they appear.
Examples
| values | ops | result |
|---|---|---|
[1, 2, 3, 4, 5] | [[2, 0, 4], [1, 1, 3, 10], [2, 0, 2], [2, 3, 4]] | [15, 26, 19] |
[0, 0, 0] | [[1, 0, 2, -4], [1, 1, 1, 6], [2, 1, 2], [2, 0, 0]] | [-2, -4] |
Example 1 — After adding 10 to positions 1..3 the array is [1, 12, 13, 14, 5].
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(values: int[], ops: int[][]) → long[]
Constraints
-
values.length,ops.length -
values[i],x -
lrin every command - At least one
2command exists. Sums can exceed 32 bits but fit in 64 bits.
Expected complexity
- Time
- O((N + Q) log N)
- Space
- O(N)
Examples
| values | ops | Expected |
|---|---|---|
[1,2,3,4,5] | [[2,0,4],[1,1,3,10],[2,0,2],[2,3,4]] | [15,26,19] |
[0,0,0] | [[1,0,2,-4],[1,1,1,6],[2,1,2],[2,0,0]] | [-2,-4] |
Hint
Hint
Use a segment tree with lazy propagation (store each node's sum and a pending add; stop as soon as an update covers a whole
node), or two Fenwick trees over the difference array: the prefix sum of the first i+1 cells is
. Keep sums in 64 bits. Looping over each range directly is and
exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1916 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |