当前位置:   article > 正文

基础算法之前缀和于差分_前缀和套差分

前缀和套差分

前缀和

这里我们讨论一维前缀和与二维前缀和,分别应用于一维序列和二维矩阵序列,主要的操作有两个,一是求出前缀和序列,二是根据前缀和求出某个区间的和,其中二维前缀和的两个操作都应用到了容斥原理,需要注意的一点是,如果题目对空间的要求比较高,那么我们可以考虑只用一个数组来保存前缀和,而不需要数组来记录数据,以节省空间,

  1. for (int i = 1; i <= n; i++) {
  2. cin >> a[i];
  3. b[i] = b[i - 1] + a[i];
  4. }
  5. int x = b[r] - b[l - 1];
  6. for (int i = 1; i <= n; i++) {
  7. for (int j = 1; j <= m; j++) {
  8. cin >> a[i][j];
  9. b[i][j] = a[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
  10. }
  11. }
  12. int x = b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1];

利用前缀和线性求最大子列和,里面应该还有别的思想,但是理解不了,暂时先记住

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 5;
  4. int a[N], b[N];
  5. int main() {
  6. int n;
  7. cin >> n;
  8. for (int i = 1; i <= n; i++) {
  9. cin >> a[i];
  10. b[i] = b[i - 1] + a[i];
  11. }
  12. int Min = 1e9;
  13. int ans = -1e9;
  14. for (int i = 1; i <= n; i++) {
  15. Min = min(Min, b[i - 1]);
  16. ans = max(ans, b[i] - Min);
  17. }
  18. cout << ans;
  19. return 0;
  20. }

差分

这里说的是序列差分,首先是一维差分和二维差分,也是对应一维序列二维序列,差分也是主要有两个操作,一是求差分序列,而是对差分序列进行修改,最后求前缀和序列以O(1)实现区间修改,所以可以看出,差分是前缀和的逆运算,同时差分具有局限性,一大堆的查询操作在最后那么适用,如果一边有修改一边有查询那么就要看时间复杂度够不够了,

  1. for (int i = 1; i <= n; i++) {
  2. cin >> a[i];
  3. b[i] = a[i] - a[i - 1];
  4. }
  5. b[x1]++;
  6. b[x2 + 1]--;
  7. for (int i = 1; i <= n; i++) {
  8. for (int j = 1; j <= m; j++) {
  9. cin >> a[i][j];
  10. b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
  11. }
  12. }
  13. b[x1][y1]++;
  14. b[x2 + 1][y1]--;
  15. b[x1][y2 + 1]--;
  16. b[x2 + 1][y2 + 1]++;

还有差分套差分,等掌握了再总结

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/569325
推荐阅读
相关标签
  

闽ICP备14008679号