区域和检索 - 数组不可变(前缀和记录)1

在本文中，我们将深入探讨一个名为“区域和检索 - 数组不可变”的问题，以及如何通过实现一个名为`NumArray`的类来解决这个问题。这个问题主要涉及数组操作和前缀和的概念，这是数据结构和算法中的重要概念。 我们要理解问题的要求。给定一个整数数组`nums`，我们需要能够快速地计算数组中任意子区间[i, j]（包括i和j）的元素之和。为了满足这一需求，我们创建了一个`NumArray`类，它具有两个核心方法：构造函数`NumArray(int[] nums)`和`int sumRange(int i, int j)`。 1. **构造函数** `NumArray(int[] nums)`： 这个构造函数用于初始化`NumArray`对象。在初始化过程中，我们创建了一个名为`sums`的`vector<int>`，其大小比输入数组`nums`大1。这个额外的空间是为了方便计算前缀和。我们遍历输入数组`nums`，将每个元素累加到`sums`中，使得`sums[i]`表示数组`nums`前`i-1`个元素的总和。这样，我们就可以在常数时间内获取任何前缀和。 ```cpp NumArray(vector<int>& nums) { sums.resize(nums.size() + 1); for (int i = 0; i < nums.size(); i++) { sums[i + 1] = sums[i] + nums[i]; } } ``` 2. **方法** `int sumRange(int left, int right)`： 这个方法接收两个整数参数`left`和`right`，表示我们想要查询的子区间的起始和结束位置。要计算这个区间的和，我们可以直接从`sums`向量中获取前缀和。`sums[right + 1]`表示包含`right`位置在内的所有元素的和，而`sums[left]`表示`left - 1`位置之前的所有元素的和。因此，子区间[i, j]的和可以通过`sums[right + 1] - sums[left]`得到。 ```cpp int sumRange(int left, int right) { return sums[right + 1] - sums[left]; } ``` 在提供的示例中，我们创建了一个`NumArray`对象`numArray`，然后对不同的子区间进行了求和操作。例如，`numArray.sumRange(0, 2)`返回1，因为`(-2) + 0 + 3`等于1，`numArray.sumRange(2, 5)`返回-1，因为`(3 + (-5) + 2 + (-1))`等于-1，最后`numArray.sumRange(0, 5)`返回-3，对应整个数组的和。 在实际应用中，这种数据结构可以用于需要频繁查询数组子区间和的场景，如动态规划、区间统计等。由于我们预先计算了前缀和，所以查询操作的时间复杂度为O(1)，大大提高了效率。然而，这种方法的空间复杂度较高，为O(n)，其中n是数组的长度。如果内存限制严格，可能需要考虑其他解决方案，如平衡二叉搜索树（如AVL树或红黑树），它们可以在O(log n)的时间内完成范围查询。