c++前缀和

### C++ 中前缀和的概念 前缀和是一种用于快速计算区间和的数据结构技术。对于给定的一个数组 `arr`，其对应的前缀和数组 `prefixSum` 定义如下： \[ \text{prefixSum}[i] = \sum_{j=0}^{i}\text{arr}[j],\quad 0 \leq i < n \] 通过构建前缀和数组，可以在常数时间内完成任意子区间的求和操作。 ### 前缀和的实现方法 #### 方法一：显式创建前缀和数组 这种方法适用于需要频繁查询不同区间的场景。先遍历一次原数组来建立前缀和数组，之后每次查询某个区间 `[l, r]` 的和只需执行简单的减法运算即可得到结果。 ```cpp vector<int> prefix_sum(const vector<int>& nums) { int n = static_cast<int>(nums.size()); vector<int> res(n); if (!n) return res; res[0] = nums[0]; for (int i = 1; i < n; ++i) res[i] = res[i - 1] + nums[i]; return res; } ``` 利用上述函数生成的前缀和数组可以轻松获取任何连续子序列之和: ```cpp // 计算闭区间[l,r]内元素总和 int range_sum(const vector<int>& pre_sums, int l, int r){ if(l == 0) return pre_sums[r]; else return pre_sums[r] - pre_sums[l-1]; } ``` #### 方法二：基于哈希表优化的空间复杂度O(1) 当只需要找到特定条件下的最远距离而非具体数值时，可以通过维护一个哈希映射来追踪首次遇见某值的位置，从而节省空间开销并提高效率[^2]. ```cpp class Solution { public: int findMaxLength(vector<int>& nums) { unordered_map<int,int> hash; hash[0]=-1; // 默认有一个前缀为0的情况 int sum=0, ret=0; for(int i=0;i<nums.size();++i) { sum += nums[i]?1:-1; // 将输入转换成相对偏移量 auto it = hash.find(sum); if(it != end(hash)) ret = max(ret, i-it->second); else hash.emplace(sum, i); } return ret; } }; ``` 这段代码展示了如何不实际存储整个前缀和列表而解决问题的方法。它巧妙地运用了哈希表来跟踪已经遇到过的累积差异及其最早出现的位置，进而实现了更高效的解决方案。 ### 应用实例 前缀和技术广泛应用于各种编程竞赛题目以及实际项目开发当中，比如解决最大子序和问题、二维平面内的矩形面积统计等问题。此外，在处理大数据集上的实时分析需求方面也表现出色，因为它能够显著减少重复累加带来的性能损耗。