303. Range Sum Query - Immutable - Explanation

Problem Link



1. Brute Force

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

    def sumRange(self, left, right):
        res = 0
        for i in range(left, right + 1):
            res += self.nums[i]
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n) for each sumRange()sumRange() query.
  • Space complexity: O(1)O(1) since we only make a reference to the input array.

2. Prefix Sum - I

class NumArray:
    def __init__(self, nums):
        self.prefix = []
        cur = 0
        for num in nums:
            cur += num
            self.prefix.append(cur)

    def sumRange(self, left, right):
        rightSum = self.prefix[right]
        leftSum = self.prefix[left - 1] if left > 0 else 0
        return rightSum - leftSum

Time & Space Complexity

  • Time complexity: O(1)O(1) for each sumRange()sumRange() query, O(n)O(n) for building the prefix sum array.
  • Space complexity: O(n)O(n)

3. Prefix Sum - II

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]


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

Time & Space Complexity

  • Time complexity: O(1)O(1) for each sumRange()sumRange() query, O(n)O(n) for building the prefix sum array.
  • Space complexity: O(n)O(n)

4. Segment Tree

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)

Time & Space Complexity

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