Range Sum Query - Immutable

Easy · Arrays & Hashing · Explanation and code example

Segment Tree

How it works

A segment tree is a binary tree where each node stores the sum of a range of elements. The root contains the sum of the entire array, and each leaf contains a single element. While this is overkill for an immutable array (prefix sums are simpler and faster), segment trees become essential when updates are needed. For this immutable version, queries still run in logarithmic time.

Steps

  1. Build the segment tree:
    • Store leaf values at indices n to 2n - 1.
    • Compute internal nodes bottom-up: tree[i] = tree[2*i] + tree[2*i + 1].
  2. For each sumRange(left, right) query:
    • Shift left and right to leaf positions.
    • While left < right:
      • If left is odd, add tree[left] to the result and increment left.
      • If right is odd, decrement right and add tree[right] to the result.
      • Move both pointers to their parents.
  3. Return the accumulated sum.

Complexity

  • Time complexity: O(log n) for each sumRange() query, O(n) for building the Segment Tree.
  • Space complexity: O(n)

Things to watch for

Off-by-One Error When Left Index Is Zero

When using a prefix sum array where prefix[i] represents the sum from index 0 to i, computing sumRange(0, right) requires special handling. Attempting to access prefix[-1] causes an error. The fix is either to check if left > 0 before subtracting, or use a prefix array of size n + 1 where prefix[0] = 0 so that prefix[right + 1] - prefix[left] always works without edge cases.

Modifying the Original Array After Preprocessing

Since prefix sums are precomputed during initialization, any subsequent changes to the original array will not be reflected in query results. This approach only works for immutable arrays. If updates are needed, a different data structure like a segment tree or Fenwick tree must be used instead of static prefix sums.

Python code example

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        left += self.n
        right += self.n + 1
        res = 0
        while left < right:
            if left % 2 == 1:
                res += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                res += self.tree[right]
            left //= 2
            right //= 2
        return res

class NumArray:
    def __init__(self, nums):
        self.segTree = SegmentTree(nums)

    def sumRange(self, left, right):
        return self.segTree.query(left, right)

C++ code example

class SegmentTree {
private:
    vector<int> tree;
    int n;

public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        tree.resize(2 * n);
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    int query(int left, int right) {
        int sum = 0;
        left += n;
        right += n + 1;
        while (left < right) {
            if (left % 2 == 1) sum += tree[left++];
            if (right % 2 == 1) sum += tree[--right];
            left /= 2;
            right /= 2;
        }
        return sum;
    }
};

class NumArray {
private:
    SegmentTree segTree;

public:
    NumArray(const vector<int>& nums) : segTree(nums) {}

    int sumRange(int left, int right) {
        return segTree.query(left, right);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations