一维数组中的前缀和
先看一道例题,力扣第303题。
区域和检索——数组不可变
没学过前缀和之前我们都会这样写。
class NumArray { private: vector<int> nums; public: NumArray(vector<int>& nums) { this->nums=nums; } int sumRange(int left, int right) { int res=0; for(int i=left;i<=right;i++) { res+=nums[i]; } return res; } };
这样写没问题,但是效率很低,sumRange会被频繁的调用，时间复杂度为O(n)。
而这道题如果利用前缀和来解题,时间复杂度就会降到O(1).
简单先介绍下前缀和:核心思想就是，创建一个新数组sum出来,用sum[i]记录num[0,1,,,,i-1]的和。
如果我们想求索引区间[1,3]内所有元素的和,S[4]-s[1]就可以得出来,这样只需要做一次减法就可以得出来结果避免了多次for循环的调用，时间复杂度为O(1).
优化后的代码:
class NumArray { public: vector<int> sum; NumArray(vector<int>& nums) { int n=nums.size(); sum.resize(n+1); // 计算sum的累加和 for(int i=0;i<n;i++) { sum[i+1]=sum[i]+nums[i]; } } /* 查询闭区间 [left, right] 的累加和 */ int sumRange(int left, int right) { return sum[right+1]-sum[left]; } };
趁热打铁再试一题:
#include<iostream> using namespace std; const int N=100010; int n,m; int a[N],sum[N]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) sum[i+1]=sum[i]+a[i]; while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum[r]-sum[l-1]); } return 0; }
前面我有一篇关于蓝桥杯的博客,里面的K倍区间就是对前缀和的应用，不过那道题对前缀和做了优化,想深入了解的可以看下:蓝桥杯——2017第八届C/C++真题[省赛][B组]_skeet follower的博客-CSDN博客
二维矩阵中的前缀和
首先介绍下二维矩阵的前缀和，这篇文章写的很好前缀和，这里我就拿大佬的思路来供我们参考学习.
步骤一：求 preSum
我们先从如何求出二维空间的 preSum[i][j]。
我们定义 preSum[i][j]preSum[i][j] 表示 从 [0,0][0,0] 位置到 [i,j][i,j] 位置的子矩形所有元素之和。
可以用下图帮助理解：
S(O, D) = S(O, C) + S(O, B) - S(O, A) + D
减去 S(O, A)S(O,A) 的原因是 S(O, C)S(O,C) 和 S(O, B)S(O,B) 中都有 S(O, A)S(O,A)，即加了两次 S(O, A)S(O,A)，所以需要减去一次 S(O, A)S(O,A)。
如果求 preSum[i][j]preSum[i][j] 表示的话，对应了以下的递推公式：
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i][j]
步骤二：根据 preSum 求子矩形面积
前面已经求出了数组中从 [0,0][0,0] 位置到 [i,j][i,j] 位置的 preSum。下面要利用 preSum[i][j]preSum[i][j] 来快速求出任意子矩形的面积。
同样利用一张图来说明：
S(A, D) = S(O, D) - S(O, E) - S(O, F) + S(O, G)
加上子矩形 S(O, G)S(O,G) 面积的原因是 S(O, E)S(O,E) 和 S(O, F)S(O,F) 中都有 S(O, G)S(O,G)，即减了两次 S(O, G)S(O,G)，所以需要加上一次 S(O, G)S(O,G)。
如果要求 [row1, col1][row1,col1] 到 [row2, col2][row2,col2] 的子矩形的面积的话，用 preSum 对应了以下的递推公式：
preSum[row2][col2] - preSum[row2][col1 - 1] - preSum[row1 - 1][col2] + preSum[row1 - 1][col1 - 1]
二维区域和检索——矩阵不可变
代码
class NumMatrix { public: vector<vector<int>> sums; NumMatrix(vector<vector<int>>& matrix) { int m = matrix.size(); if (m > 0) { int n = matrix[0].size(); sums.resize(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j]; } } } } int sumRegion(int row1, int col1, int row2, int col2) { return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1]; } };
代码
#include<iostream> using namespace std; const int N=1010; int n,m,q; int a[N][N],s[N][N]; int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; } } while(q--) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]); } return 0; }
