iq.lab
Python starts when a code cell comes near or you run one
easyPrefix sumsDesign as coding target 15 min

Range sum query

Not solved yetLeetCode 303. Range Sum Query - Immutable

You get a list of integers nums that never changes, followed by many questions about it. Each question gives two positions, left and right, and wants the total of the items from position left through position right, both ends included.

Write a class NumArray. Its constructor (the __init__ method, which runs once when you write NumArray(nums)) receives the list. Its method sum_range(left, right) answers one question by returning that total. One object can get up to 100,000 questions, so the work per question has to be small. (LeetCode spells the method sumRange.)

Example 1
InputNumArray([3, -1, 4, 2, 5]), then sum_range(0, 2), sum_range(1, 3), sum_range(4, 4)Output6, 5, 5

3 + (-1) + 4 = 6, then (-1) + 4 + 2 = 5, then the single item at position 4, which is 5.

Example 2
InputNumArray([4, -2, 1, 0, 6]), then sum_range(0, 4), sum_range(1, 2), sum_range(3, 3)Output9, -1, 0

The whole list adds up to 9. Positions 1 and 2 give -2 + 1 = -1. Position 3 alone gives 0: a range can be one item.

Constraints

  • 1 ≤ len(nums) ≤ 105

  • -105 ≤ nums[i] ≤ 105

  • 0 ≤ left ≤ right < len(nums)

  • Up to 105 calls to sum_range on one object.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

⌘+Enter runs 0:00Python starts when a code cell comes near or you run one
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern