Skip to content

303. Range Sum Query - Immutable

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class NumArray {
 public:
  NumArray(vector<int>& nums) : prefix(nums.size() + 1) {
    partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
  }

  int sumRange(int left, int right) {
    return prefix[right + 1] - prefix[left];
  }

 private:
  vector<int> prefix;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class NumArray {
  public NumArray(int[] nums) {
    prefix = new int[nums.length + 1];
    for (int i = 0; i < nums.length; ++i)
      prefix[i + 1] = nums[i] + prefix[i];
  }

  public int sumRange(int left, int right) {
    return prefix[right + 1] - prefix[left];
  }

  private int[] prefix;
}

1
2
3
4
5
6
class NumArray:
  def __init__(self, nums: List[int]):
    self.prefix = [0] + list(itertools.accumulate(nums))

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