算法工具箱之前缀和

前缀和概念前缀和Prefix Sum是一种重要的预处理技术能够在O(1)时间内快速计算数组任意区间的和。核心思想对于数组nums我们预先计算一个前缀和数组prefix其中prefix[i]表示nums[0]到nums[i]的和一维前缀和#includeiostream #includevector using namespace std; int main() { long long n,m; cinnm; vectorlong long arr1(n); vectorlong long arr2(n 1); arr2[0] 0; for(auto x : arr1) { scanf(%d,x); } for(int j 1;j arr2.size();j) { arr2[j] arr2[j-1] arr1[j-1]; } long long l,r; for(int i 0;i m;i) { cinlr; coutarr2[r] - arr2[l - 1]endl; } return 0; }算法思路先构建一个比原数组长度1的前缀和数组再将arr2[0] 0然后⽤ arr2[i] 表⽰ [1, i] 区间内所有元素的和那么 arr2[i - 1] ⾥⾯存的就是 i - 1 区间内所有元素的和那么可得递推公式arr2[i] arr2[i - 1] arr1[i]。使⽤前缀和数组「快速」求出「某⼀个区间内」所有元素的和当询问的区间是[l, r] 时区间内所有元素的和为arr2[r] - arr2[l - 1]。算法优势1查询高效将O(n)的区间求和优化为O(1)的差值计算2预处理思想一次构建多次使用3扩展性强可扩展到二维、多维情况二位前缀和#includeiostream #includevector using namespace std; int main() { int m, n, q; cin m n q; vectorvectorint arr(m, vectorint(n)); vectorvectorlong long arr2(m 1, vectorlong long(n 1)); for (int i 0; i m; i) { for (int j 0; j n; j) { cin arr[i][j]; } } vectorvectorint arr1(q, vectorint(4)); for (int x 0; x q; x) { for (int i 0; i 4; i) { cin arr1[x][i]; } } for (int i 1; i m; i) { for (int j 1; j n; j) { arr2[i][j] arr2[i - 1][j] arr2[i][j - 1] arr[i - 1][j - 1] - arr2[i - 1][j - 1]; } } for (int i 0; i q; i) { int x1 arr1[i][0], y1 arr1[i][1], x2 arr1[i][2], y2 arr1[i][3]; cout arr2[x2][y2] - arr2[x1 - 1][y2] - arr2[x2][y1 - 1] arr2[x1 - 1][y1 - 1] endl; } return 0; }算法思路类⽐于⼀维数组的形式如果我们能处理出来从 元素的累加和就可以在 [0, 0] 位置到 [i, j] 位置这⽚区域内所有 O(1) 的时间内搞定矩阵内任意区域内所有元素的累加和。1搞出来前缀和矩阵这⾥就要⽤到⼀维数组⾥⾯的拓展知识我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列 0这样我们就可以省去⾮常多的边界条件的处理。我们填写前缀和矩阵数组的时候下标直接从 1 开始能⼤胆使⽤ i - 1 , j - 1 位 置的值。递归方程就是s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]a[i][j]黄 新格子a[i][j]红蓝s[i-1][j]上一行到 j 列的和红绿s[i][j-1]这一行到 j-1 列的和红s[i-1][j-1]上一行 j-1 列的和所以红蓝红绿红蓝绿红红多算了一次因此s[i][j](红蓝)(红绿)−红黄。2查询公式求子矩阵和查询(x1,y1)到(x2,y2)的和sums[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]用颜色划分理解把整个大矩形s[x2][y2]分成四个区域D 我们要查询的子矩阵(x1,y1)到(x2,y2)ABCDs[x2][y2]ABs[x1-1][y2],ACs[x2][y1-1],As[x1-1][y1-1]。所以D(ABCD)−(AB)−(AC)A即Ds[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1]。后缀和概念从一个元素开始到数组末尾的所有元素之和。具体来说给定一个数组nums它的后缀和数组suffixSum是另一个数组其中每个元素suffixSum[i]的定义如下suffixSum[i] nums[i] nums[i1] ... nums[n-1]。这里n是数组nums的长度。计算后缀和的步骤从后往前遍历。与前缀和思想类似例题class Solution { public: int pivotIndex(vectorint nums) { int ret -1; vectorint arr1(nums.size(), 0); vectorint arr2(nums.size(), 0); int x arr1.size() - 1; for (int i 1; i nums.size(); i) { arr1[i] arr1[i - 1] nums[i - 1]; } for (int i x-1; i 0; i--) { arr2[i] arr2[i1] nums[i 1]; } for (int i 0; i nums.size(); i) { if (arr1[i] arr2[i]) { return i; } } return ret; } };核心思路我们要寻找一个下标i使得左侧和 右侧和所以我们发现只要前缀和和后缀和相等那么这个中心下标就是这个i。