Range Sum Query - Immutable

Easyarrayprefix-sum
Category: System Design
Companies that ask this question:
AmazonGoogle
LeetCode →

Approach

Range Sum Query - Immutable

Approach

Use prefix sum array for O(1) range queries.

Algorithm

  1. Build prefix sum array during initialization:
    • prefix[i] = sum of elements from index 0 to i-1
  2. For range query [left, right]:
    • Return prefix[right+1] - prefix[left]

Complexity

  • Time: O(n) initialization, O(1) per query
  • Space: O(n) - prefix sum array

Key Insights

  • Trade space for query time efficiency
  • Prefix sum enables constant time range queries
  • Works well when array is immutable (no updates)

Solution

java
1class NumArray {
2    private int[] prefix;
3    
4    public NumArray(int[] nums) {
5        prefix = new int[nums.length + 1];
6        for (int i = 0; i < nums.length; i++) {
7            prefix[i + 1] = prefix[i] + nums[i];
8        }
9    }
10    
11    public int sumRange(int left, int right) {
12        return prefix[right + 1] - prefix[left];
13    }
14}
Loading visualizer...