Funcia
Lv.3fenwick-treesegment-tree

Range Sum with Updates

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

Process the commands in ops on the array values in order: [1, i, x] sets values[i] = x; [2, l, r] asks for values[l] + … + values[r]. Return the answers to the 2 commands in order.

Examples

valuesopsresult
[1, 2, 3, 4, 5][[2, 0, 4], [1, 2, 10], [2, 1, 3], [2, 2, 2]][15, 16, 10]
[-5, 5][[1, 0, 7], [1, 0, -1], [2, 0, 1]][4]

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,Q≤200,0001 \le N, Q \le 200{,}000; −109≤-10^9 \le values[i], x ≤109\le 10^9
  • [1, i, x]: 0≤i<N0 \le i < N; [2, l, r]: 0≤l≤r<N0 \le l \le r < N
  • At least one 2 command exists. Sums can exceed 32 bits.

Expected complexity

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

Examples

valuesopsExpected
[1,2,3,4,5][[2,0,4],[1,2,10],[2,1,3],[2,2,2]][15,16,10]
[-5,5][[1,0,7],[1,0,-1],[2,0,1]][4]

Hint

Hint

Use a Fenwick tree (or segment tree): point update add(i, x - cur[i]), range sum prefix(r + 1) - prefix(l), both O(log⁡N)O(\log N), with 64-bit sums. Summing each range directly, or rebuilding prefix sums after each update, is O(NQ)O(NQ).

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.