Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

303. Range Sum Query - Immutable

Time: $O(n)$

Space: $O(n)$

			


class NumArray {
 public:
  NumArray(vector<int>& nums) : prefix(nums.size() + 1) {
    partial_sum(begin(nums), end(nums), begin(prefix) + 1);
  }

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

 private:
  vector<int> prefix;
};




			


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;
}




			


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]