Lv.3fenwick-treesegment-tree
Range Sum with Updates
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| values | ops | result |
|---|---|---|
[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
- ;
values[i],x [1, i, x]: ;[2, l, r]:- At least one
2command exists. Sums can exceed 32 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,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
, with 64-bit sums. Summing each range directly, or rebuilding prefix sums after each update, is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 266 ms | estimated |
| C++ (GCC, gnu++23) | 266 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 2072 ms | derived |
| Kotlin 2.4 (JVM) | 1532 ms | estimated |
| C# 14 (.NET 10) | 1532 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 8 | verdict only |
| performance | 60 | 4 | verdict only |