Funcia
Lv.1arrayprefix-sum

Prefix Sum Queries

Memory limit
256 MB
Correctness time limit
10000 ms
Acceptance
100.0%
Solvers
1
0

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

  • 1≤1 \le values.length ≤200,000\le 200{,}000, −109≤-10^9 \le values[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000, 0≤l≤r<0 \le l \le r < 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: O(N+Q)O(N + Q). Summing each range directly, O(N×Q)O(N \times Q), exceeds the performance time limit.

Function signature

solution(values: long[], queries: int[][]) → long[]

Expected complexity

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

Examples

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

LanguageEfficiency time limit
C (GCC, gnu17)246 msestimated
C++ (GCC, gnu++23)246 msderived
Python 3.131000 msderived
Java 252122 msderived
Kotlin 2.4 (JVM)1492 msestimated
C# 14 (.NET 10)1492 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.