Asked at

Range Sum Query

Medium
VerifiedArrayPrefix Sum~20 min

Given nums and a list of queries where each queries[i] = [l, r], return an array of sums, one per query, covering nums[l..r] inclusive.

Precompute prefix sums so each query answers in O(1). The input arrives as a single object { nums, queries }.

Examples

in{ nums: [1, 2, 3, 4, 5], queries: [[0, 2], [1, 3], [0, 4]] }
out[6, 9, 15]

Sums of nums[0..2], nums[1..3], nums[0..4].

in{ nums: [-2, 0, 3, -5, 2, -1], queries: [[0, 2], [2, 5]] }
out[1, -1]

nums[0..2] = 1 and nums[2..5] = -1.

Constraints

  • 1 ≤ nums.length ≤ 10⁴
  • 0 ≤ queries.length ≤ 10⁴
  • queries[i] == [l, r] with 0 ≤ l ≤ r < nums.length
  • -10⁵ ≤ nums[i] ≤ 10⁵
  • Target: O(n + q) time.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.