前缀和 有图文 超详细整理通俗易懂

前缀和是什么

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

【模板】前缀和

题目链接

我们很容易想出暴力解法，遍历区间求和。

这样的时间复杂度为O(n * m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n + m)，大大提高了运算效率。

而我们用前缀和的话，时间复杂度为O(1)

原理：

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] … a[r];
sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];
sum[r] - sum[l - 1] = a[l] + a[l + 1] + …+ a[r];

这样，对于每个询问，只需要执行 sum[r] - sum[l - 1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。

我们把它叫做一维前缀和。

int main() {int n, q;cin >> n >> q;vector<int> v(n);for(int i = 0; i <n; i++)cin>>v[i];vector<long long> dp(n+1); //dp[i]表示 1 ~ i 总和 for(int i = 1; i<=n; i++) dp[i] = dp[i-1] + v[i-1];int l , r;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}
// 64 位输出请用 printf("%lld")

【模板】二维前缀和

题目链接

紫色面积是指(1, 1)左上角到(i, j - 1)右下角的矩形面积, 绿色面积是指(1, 1)左上角到(i - 1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。

从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i - 1][j] + 紫色面积s[i][j - 1] - 重复加的红色的面积s[i - 1][j - 1] + 小方块的面积a[i][j];

因此得出二维前缀和预处理公式

s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i] [j] - s[i - 1][j - 1]

接下来回归问题去求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和。

因此二维前缀和的结论为：

以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

int main() {int n,m,q;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){cin >> arr[i][j];}}vector<vector<long long>> dp(n+1,vector<long long>(m+1));//防止溢出for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];}}int x1,x2,y1,y2;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;}return 0;
}

寻找数组的中心下标

题目链接

这里我们用 前缀和 和 后缀和 来解决问题

class Solution {
public:int pivotIndex(vector<int>& nums) {vector<int> f(nums.size());  //f[i]表示[0,i-1]区间，所有元素和vector<int> g(nums.size());  //g[i]表示[i+1,n-1]区间，所有元素和for(int i = 1; i<nums.size(); i++){f[i] = f[i-1] + nums[i-1];}for(int i = nums.size() - 2; i>=0; i--){g[i] = g[i+1] + nums[i+1];}for(int i = 0; i<nums.size(); i++){if(f[i] == g[i])return i;}return -1;}
};

和为 K 的子数组

题目链接

我们对数组 0~i 位置分析，以 i 位置为结尾的所有的子数组 ， 然后我们只需要找在【0，i-1】区间内，有多少个前缀和等于 sum[i] - k；

细节问题：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0] = 1;int sum = 0,ret = 0;for(auto x : nums){sum += x; //计算前缀和if(hash.count(sum-k)) ret+=hash[sum-k];//统计个数hash[sum]++;} return ret;}
};