0303. 区域和检索 - 数组不可变 Range Sum Query - Immutable

问题描述

这个问题就是要使用 前缀和数组 prefix sum array, 详细的内容可以参阅前文的介绍.

实现方法也很直接:

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct NumArray {
    prefix_sum: Vec<i32>,
}

impl NumArray {
    pub fn new(nums: Vec<i32>) -> Self {
        assert!(!nums.is_empty());
        let mut prefix_sum = vec![0; nums.len()];
        prefix_sum[0] = nums[0];

        for i in 1..nums.len() {
            prefix_sum[i] = nums[i] + prefix_sum[i - 1];
        }
        Self { prefix_sum }
    }

    #[must_use]
    pub fn sum_range(&self, left: i32, right: i32) -> i32 {
        let left = left as usize;
        let right = right as usize;
        debug_assert!(left <= right);

        if left == 0 {
            self.prefix_sum[right]
        } else {
            self.prefix_sum[right] - self.prefix_sum[left - 1]
        }
    }
}
}

算法的时间复杂度是 O(1), 空间复杂度是 O(n).