💬 Discord
Sign In
NeetCode #53LC-303EasyArrays & Hashing
← Back to All Problems

#53 · #303 · Range Sum Query - Immutable(区域和检索 - 数组不可变)

📌 Problem Statement & Constraints

Design a class that answers sum queries on an immutable array. Implement NumArray(nums) and sumRange(left, right), returning the sum of nums[left..right] inclusive. Constraints: 1 <= nums.length <= 10^4, up to 10^4 queries.

💡 Core Algorithmic Approaches

  1. Recomputing the sum per query is O(n), which is too slow for 10^4 queries over a 10^4 array.
  2. Precompute a prefix-sum array P of length n + 1, where P[i] is the sum of the first i elements and P[0] = 0.
  3. Then sumRange(l, r) = P[r + 1] - P[l], in O(1).
  4. The leading zero is what makes the formula work uniformly for l == 0 without a special case.

💻 Benchmark Python3 Implementation

class NumArray:
    def __init__(self, nums: List[int]):
        # P[i] = sum of nums[0..i-1]; the leading 0 removes boundary cases
        self.P = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.P[i + 1] = self.P[i] + x

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) to build, then O(1) per query. The brute-force alternative is O(n) per query.
💾 Space Complexity
O(n) for the prefix array.

⚠️ Interview Pitfalls & Follow-ups

  • Indexing the prefix array as P[right] - P[left]: off by one; the correct form uses P[right + 1].
  • Omitting the leading zero: then left == 0 requires a branch, and negative indices silently produce wrong answers in Python.
  • Summing lazily and caching: works, but the immutable guarantee is exactly what makes the one-shot prefix build the right choice.