FAANG · LeetCode #303

Range Sum Query — Immutable — three-stage drill

1The ProblemEasy

Range Sum Query — Immutable

Answer many sumRange(l, r) queries on a fixed array.

Examples

sumRange(1,3) on [2,4,1,5,3]→ 10sumRange(0,4)→ 15

constraintArray never changes (immutable); many queries.

2The PatternTIME O(n) · SPACE O(n)

Prefix Sum

Running cumulative totals turn range-sum questions into O(1) lookups.

Problems using this pattern

3The SolutionRESULT → O(1)

Step through it

P[0] = 0 (sum of nothing)

Step 1 / 9

Python▎range sum = P[r+1] − P[l]

1class NumArray:
2    def __init__(self, nums):
3        self.P = [0]
4        for x in nums:
5            self.P.append(self.P[-1] + x)
6 
7    def sumRange(self, l, r):
8        return self.P[r + 1] - self.P[l]

why it worksThis is the foundational prefix-sum move. Build P once (P[i] = sum of the first i values), then any range sum is a single subtraction: sum of nums[l..r] = P[r+1] − P[l]. Each query is O(1) instead of O(n) re-summing — which is exactly why prefix sums exist.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Range Sum Query — Immutable — three-stage drill