Range sum query mutable

Array Divide and Conquer Design Binary Indexed Tree Segment Tree

42.6% acceptance

Feb 27, 2026

5114

269

Given an integer array nums, handle multiple queries of the following types: Update the value of an element in nums. 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. void update(int index, int val) Updates the value of nums[index] to be val. 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 update(&self, index: i32, val: i32) {

 *     }

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

 *     }
 * }
 */

use std::cell::RefCell;
impl NumArray {
  fn new(nums: Vec<i32>) -> Self {
    let n = nums.len();
    let mut tree = vec![0; n * 4];
    let nums_clone = nums.clone();
    Self::build_tree(&nums, &mut tree, 0, 0, n - 1);
    NumArray {
      nums: RefCell::new(nums_clone),
      tree: RefCell::new(tree),
    }
  }
  
  fn build_tree(nums: &[i32], tree: &mut [i32], node: usize, start: usize, end: usize) {
    if start == end {
      tree[node] = nums[start];
    } else {
      let mid = start + (end - start) / 2;
      Self::build_tree(nums, tree, 2 * node + 1, start, mid);
      Self::build_tree(nums, tree, 2 * node + 2, mid + 1, end);
      tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
  }
  
  fn update(&self, index: i32, val: i32) {
    let index = index as usize;
    let n = self.nums.borrow().len();
    let mut nums = self.nums.borrow_mut();
    let mut tree = self.tree.borrow_mut();
    nums[index] = val;
    Self::update_tree(&mut tree, 0, 0, n - 1, index, val);
  }
  
  fn update_tree(tree: &mut [i32], node: usize, start: usize, end: usize, index: usize, val: i32) {
    if start == end {
      tree[node] = val;
    } else {
      let mid = start + (end - start) / 2;
      if index <= mid {
        Self::update_tree(tree, 2 * node + 1, start, mid, index, val);
      } else {
        Self::update_tree(tree, 2 * node + 2, mid + 1, end, index, val);
      }
      tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
  }
  
  fn sum_range(&self, left: i32, right: i32) -> i32 {
    let left = left as usize;
    let right = right as usize;
    let n = self.nums.borrow().len();
    let tree = self.tree.borrow();
    Self::query_tree(&tree, 0, 0, n - 1, left, right)
  }
  
  fn query_tree(tree: &[i32], node: usize, start: usize, end: usize, left: usize, right: usize) -> i32 {
    if right < start || left > end {
      return 0;
    }
    if left <= start && end <= right {
      return tree[node];
    }
    let mid = start + (end - start) / 2;
    let left_sum = Self::query_tree(tree, 2 * node + 1, start, mid, left, right);
    let right_sum = Self::query_tree(tree, 2 * node + 2, mid + 1, end, left, right);
    left_sum + right_sum
  }
}

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