Easy

Range Sum Query - Immutable

009

Given nums and a list of [left, right] queries, return the sum inside each inclusive range.

EXAMPLES

Example 1

Input
{
  "nums": [
    -2,
    0,
    3,
    -5,
    2,
    -1
  ],
  "queries": [
    [
      0,
      2
    ],
    [
      2,
      5
    ],
    [
      0,
      5
    ]
  ]
}

Output
[
  1,
  -1,
  -3
]

FUNCTION SHAPE

nums: intArrayqueries: intMatrix→intArray

SOLUTION NOTE

Direct application of prefix sum. The append(0) trick makes prefix[-1] = 0, handling the left = 0 case cleanly.

Reveal reference solution +

pythonREFERENCE

class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix = list(accumulate(nums))
        self.prefix.append(0)  # prefix[-1] = 0

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right] - self.prefix[left - 1]

TimeO(n) init, O(1) query

SpaceO(n)

Open on LeetCode ↗