Count of range sum

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

38.3% acceptance

Jan 12, 2026

2498

265

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_range_sum(nums: Vec<i32>, lower: i32, upper: i32) -> i32 {
    let n = nums.len();
    let mut prefix: Vec<i64> = vec![0; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }
    
    fn merge_sort(prefix: &mut [i64], lower: i64, upper: i64, start: usize, end: usize) -> i32 {
      if start >= end {
        return 0;
      }
      
      let mid = start + (end - start) / 2;
      let mut count = merge_sort(prefix, lower, upper, start, mid)
        + merge_sort(prefix, lower, upper, mid + 1, end);
      
      let mut j = mid + 1;
      let mut k = mid + 1;
      
      for i in start..=mid {
        while j <= end && prefix[j] - prefix[i] < lower {
          j += 1;
        }
        while k <= end && prefix[k] - prefix[i] <= upper {
          k += 1;
        }
        count += (k - j) as i32;
      }
      
      let mut temp = Vec::new();
      let mut i = start;
      let mut j = mid + 1;
      
      while i <= mid && j <= end {
        if prefix[i] <= prefix[j] {
          temp.push(prefix[i]);
          i += 1;
        } else {
          temp.push(prefix[j]);
          j += 1;
        }
      }
      
      while i <= mid {
        temp.push(prefix[i]);
        i += 1;
      }
      
      while j <= end {
        temp.push(prefix[j]);
        j += 1;
      }
      
      for (idx, &val) in temp.iter().enumerate() {
        prefix[start + idx] = val;
      }
      
      count
    }
    
    if n == 0 {
      return 0;
    }
    merge_sort(&mut prefix, lower as i64, upper as i64, 0, n)
  }
}