Funcia
Lv.3fenwick-treelazy-propagationsegment-tree

Range Add, Range Sum

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

You are given an integer array values and a list of commands ops, processed in order:

  • [1, l, r, x]: add x to every one of values[l], values[l+1], …, values[r].
  • [2, l, r]: report values[l] + values[l+1] + … + values[r].

Return the answers of the 2 commands in the order they appear.

Examples

valuesopsresult
[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

  • 1≤N=1 \le N = values.length ≤100,000\le 100{,}000, 1≤Q=1 \le Q = ops.length ≤100,000\le 100{,}000
  • −109≤-10^9 \le values[i] ≤109\le 10^9, −106≤-10^6 \le x ≤106\le 10^6
  • 0≤0 \le l ≤\le r <N< N in every command
  • At least one 2 command exists. Sums can exceed 32 bits but fit in 64 bits.

Expected complexity

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

Examples

valuesopsExpected
[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 (i+1)∑j≤idj−∑j≤idj⋅j(i+1)\sum_{j\le i} d_j - \sum_{j\le i} d_j \cdot j. Keep sums in 64 bits. Looping over each range directly is O(NQ)O(NQ) and exceeds the time limit.

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.