Lv.1arrayprefix-sum
Prefix Sum Queries
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Acceptance
- 100.0%
- Solvers
- 1
Prefix Sum Queries
Given an integer array values and a list of queries, answer each query [l, r] with
values[l] + ... + values[r] (inclusive, 0-indexed) and return the answers in query order.
Constraints
-
values.length,values[i] -
queries.length,values.length - Sums can exceed 32 bits; use 64-bit integers.
Example
values = [1, 2, 3, 4, 5], queries = [[0, 4], [1, 3], [2, 2]] → [15, 9, 3]
Expected time complexity: . Summing each range directly, , exceeds the performance time limit.
Function signature
solution(values: long[], queries: int[][]) → long[]
Expected complexity
- Time
- O(N + Q)
- Space
- O(N)
Examples
| values | queries | Expected |
|---|---|---|
[1,2,3,4,5] | [[0,4],[1,3],[2,2]] | [15,9,3] |
[-3,10,-2] | [[0,1],[1,2],[0,0]] | [7,8,-3] |
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 246 ms | estimated |
| C++ (GCC, gnu++23) | 246 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 2122 ms | derived |
| Kotlin 2.4 (JVM) | 1492 ms | estimated |
| C# 14 (.NET 10) | 1492 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 8 | verdict only |
| performance | 60 | 4 | verdict only |