303. 区域和检索 - 数组不可变
一维前缀和是处理数组区间求和问题的一种非常有效的方法。它通过预处理输入数组，使得任何区间的和都可以在常数时间内被计算出来。这种方法特别适用于处理静态数组上的大量区间求和查询，其中静态数组是指在查询过程中不会发生变化的数组。
一维前缀和定义
对于给定的数组 arr[0...n-1]，其一维前缀和数组 prefixSum[0...n] 可以定义如下：
prefixSum[0] = 0，这是为了方便计算从头开始的区间和。- 对于所有的
1 <= i <= n，prefixSum[i] = prefixSum[i-1] + arr[i-1]。也就是说，prefixSum[i]存储了arr[0...i-1]的总和。
构建前缀和数组
构建前缀和数组的过程是直接的。你只需要遍历一遍原数组，逐个累加前一个元素的前缀和与当前元素的值即可。
区间求和
前缀和数组使得计算任何区间 [l, r]（0 <= l <= r < n）内元素的总和变得极其简单和快速。区间和可以用以下公式计算：
sum(l, r) = prefixSum[r + 1] - prefixSum[l]
这个公式之所以有效，是因为 prefixSum[r + 1] 包含了 arr[0...r] 的总和，而 prefixSum[l] 包含了 arr[0...l-1] 的总和。二者之差刚好是 arr[l...r] 的总和。
示例
假设我们有一个数组 arr = [3, 7, 2, 5, 8]，我们想要快速计算出从索引 1 到 3 的区间和。
-
首先，我们构建前缀和数组
prefixSum：prefixSum = [0, 3, 10, 12, 17, 25]
-
要计算
sum(1, 3)，我们简单地用prefixSum[4] - prefixSum[1]来计算：sum(1, 3) = prefixSum[4] - prefixSum[1] = 17 - 3 = 14
因此，arr[1...3] 的区间和是 14，这个结果是通过两次数组访问和一次减法操作迅速得到的。
适用场景
一维前缀和非常适合于处理那些数组不经常变化，但需要频繁计算不同区间和的问题。在多次查询的情况下，前缀和的预计算可以显著减少总的计算时间，因为每个区间和的计算都可以在 O(1) 的时间内完成。
题目
代码解释
成员变量
int[] sum：一个数组，用于存储从数组nums的开始到当前索引的元素和。这个数组的大小是nums.length + 2，以便于处理边界条件并简化计算。这里多出来的2个空间用于处理边界情况，但实际上只需要额外1个空间即可。
构造函数
public NumArray(int[] nums)：这个构造函数接收一个整数数组nums作为输入，并使用这个数组来初始化前缀和数组sum。- 初始化
sum数组时，sum[0]通常设为0，以方便计算从数组第一个元素开始的区间和。但在这段代码中，由于从sum[1]开始存储前缀和（使得代码中的sum[i+1] = nums[i] + sum[i];成立），sum[0]自然为0，无需显式初始化。 - 通过循环遍历
nums数组，累加当前元素nums[i]到sum[i+1]中。这样，sum[i+1]就存储了nums[0]到nums[i]的总和。
- 初始化
sumRange 方法
public int sumRange(int left, int right)：这个方法接收两个参数left和right，代表要计算和的数组区间的起始和结束索引。方法通过简单地从sum[right+1]中减去sum[left]来得到区间[left, right]的元素和。- 为什么这样做是正确的？因为
sum[right+1]包含了从nums[0]到nums[right]的总和，而sum[left]包含了从nums[0]到nums[left-1]的总和。二者之差正是区间[left, right]的总和。
- 为什么这样做是正确的？因为
注释版代码
class NumArray {
// 前缀和数组
int[] sum;
public NumArray(int[] nums) {
// 初始化前缀和数组，长度为原数组长度+1，方便处理前缀和计算
sum = new int[nums.length + 1];
// 构建前缀和数组
for (int i = 0; i < nums.length; i++) {
// 当前元素的前缀和 = 当前元素值 + 前一个元素的前缀和
sum[i + 1] = nums[i] + sum[i];
}
// 用于调试的打印语句，展示前缀和数组的内容
//System.out.println(Arrays.toString(sum));
}
// 计算区间[left, right]内元素的和
public int sumRange(int left, int right) {
// 通过前缀和数组计算区间和：区间结束点的前缀和 - 区间开始点前一个元素的前缀和
return sum[right + 1] - sum[left];
}
}
这段代码是前缀和概念的一个典型应用，通过预处理将多次求区间和的操作时间复杂度从 O(n) 优化到了 O(1)。
标签：前缀,nums,int,18,sum,303,prefixSum,数组,LeetCode2024 From： https://blog.csdn.net/qq_47778153/article/details/136801642