前缀和与二维前缀和

前缀和

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

　　

 

　　如图，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 ]。

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

#include
using namespace std;
#define MAXN 100010
int n,m;
int a[MAXN],s[MAXN];
int main()
{
    cin>>n; //数组的长度 
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];  
        s[i]=s[i-1]+a[i]; //这里就是上面讲到的预处理的方法 
    }
    cin>>m; //读入区间数量 
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r; //读入区间的左边界和右边界 
        cout<1]<//输出区间和 
    }
    return 0;
} 

---

 

二维前缀和

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

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

      

　　如图，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 ]。

　　二维前缀和代码与一维差别不大，在此便不一一赘述了其实是懒得打。

　　但需要注意的是，求二维区间是，同样会有一块区域减了两次，需要再加回来，留给读者自行思考 §(*￣▽￣*)§

---

 

总结

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

 

                                                                        码字不易，点个赞呗§(*￣▽￣*)§

 

---

如果您觉得阅读本文对您有帮助，请点一下“推荐”按钮，您的“推荐”将是我最大的写作动力！欢迎各位转载，但是未经作者本人同意，转载文章之后必须在文章页面明显位置给出作者和原文连接，否则保留追究法律责任的权利。

• 前缀和
• 二维前缀和
• 总结

__EOF__