Range sum query immutable

Array Design Prefix Sum

71.5% acceptance

Jan 12, 2026

3800

2016

Given an integer array nums, handle multiple queries of the following type: Calculate the sum of the elements of nums between indices left and right inclusive where left <= right. Implement the NumArray class: NumArray(int[] nums) Initializes the object with the integer array nums. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

* impl NumArray {

 *     fn new(nums: Vec<i32>) -> Self {

 *     }

 *     fn sum_range(&self, left: i32, right: i32) -> i32 {

 *     }
 * }
 */

impl NumArray {

  fn new(nums: Vec<i32>) -> Self {
    let mut prefix_sum = vec![0; nums.len() + 1];
    for i in 0..nums.len() {
      prefix_sum[i + 1] = prefix_sum[i] + nums[i];
    }
    NumArray { prefix_sum }
  }
  
  fn sum_range(&self, left: i32, right: i32) -> i32 {
    self.prefix_sum[right as usize + 1] - self.prefix_sum[left as usize]
  }
}

/*
 * Your NumArray object will be instantiated and called as such:
 * let obj = NumArray::new(nums);
 * let ret_1: i32 = obj.sum_range(left, right);
 */