经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
前缀和与二维前缀和
来源:cnblogs  作者:yczzws  时间:2023/2/28 8:51:41  对本文有异议

前缀和

  前缀和,顾名思义,就是所有前缀之和,给一个最基本的例子:

  

 

  如图,a为原始数组,s为完成预处理后的数组,很容易看出来s[ i ]=s[ i - 1 ]+a[ i ],而也就是s[ i ]=a[1]+a[2]+……+a[ i ],需要注意的是记s[0]=0

  那么,如果我想要知道一个区间的区间和该怎么做呢?其实很简单,例如要求区间3~5的区间和,就可以用s[5]-s[2]=19-8=11。这里同样需要注意当减去区间左边界时需要将其减1,及求l~r的区间和,是用s[ r ]-s[ l-1 ]

  根据以上求区间前缀和的思路可以完成以下代码

  1. 1 #include<bits/stdc++.h>
  2. 2 using namespace std;
  3. 3 #define MAXN 100010
  4. 4 int n,m;
  5. 5 int a[MAXN],s[MAXN];
  6. 6 int main()
  7. 7 {
  8. 8 cin>>n; //数组的长度
  9. 9 for(int i=1;i<=n;i++)
  10. 10 {
  11. 11 cin>>a[i];
  12. 12 s[i]=s[i-1]+a[i]; //这里就是上面讲到的预处理的方法
  13. 13 }
  14. 14 cin>>m; //读入区间数量
  15. 15 for(int i=1;i<=m;i++)
  16. 16 {
  17. 17 int l,r;
  18. 18 cin>>l>>r; //读入区间的左边界和右边界
  19. 19 cout<<s[r]-s[l-1]<<endl; //输出区间和
  20. 20 }
  21. 21 return 0;
  22. 22 }

 

二维前缀和

  刚才介绍的一维前缀和可以用来快速一维序列的区间总和,而二维前缀和则可以快速求出一个二维矩阵中一个长方形内所以元素的总和。

  在往下说之前我们依旧先来看一张图:

      

  如图,a为原始数组,s为预处理过的数组,它们之间有什么规律吗?乍一看似乎不怎么看的出来,那就先看第一排和第一列,很容易就发现,这就是上面的前缀和,下面再看s[2][2],它与a[2][2]又有什么联系呢?仔细看会发现s[2][2]=s[2][1]+s[1][2]+a[2][2],那么规律就是如此吗?似乎并不对!那就在看一张图:

           

  图中,我们就可以看出在s[2][1]+s[1][2]相加后,会有一块被重复加了两次,所以,其实还要再减去一个s[1][1],只不过因为s[1][1]=0,所以一时未发现,综上,我们可以得到二维前缀和预处理的方法,及s[ i ,j ]=s[ i,j-1 ]+s[ i-1,j ]-s[ i-1,j-1 ]+a[ i,j ]

  二维前缀和代码与一维差别不大,再次便不赘述了其实是懒得打


 

总结

  利用前缀和我们可以在常数时间中查询区间和,这在某些方面是可以给程序带来极大的帮助,而其中耗时相对较大的二维前缀和在很多时候是可以转换从一维前缀和的做法的,此处留给读者自行思考。

 

                                                                        码字不易,点个赞呗§(* ̄▽ ̄*)§

 

原文链接:https://www.cnblogs.com/jsyczzws/p/17162238.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号