前缀和与差分(初学者）

随着编写代码的熟练大多数人容易使用区间求和：

#include
using namespace std;

int main()
{
    int n,i;
    cin>>n;
    int a[n];
    for(i=0;i>a[i];}
    int sum=0,l,r;
    cin>>l>>r;
    for(i=l;i<=r;i++){
    sum=a[i]+sum;}
    cout< 
这种数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度大幅度降低，提高运算效率。
 
1.一维前缀和： 
用于解决下标区间内的数组的和可用前缀和相减；也可扩展用于统计某个下标区间内某个数字出现的个数 
#include
using namespace std;

int main()
{  
    int n,i;
    cin>>n;
    int a[n],sum[n];
    for(i=1;i<=n;i++)
  {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
  }
    return 0;
}
 
2.二维前缀和： 
由一维前缀和拓展而来常用于解决类似   【 激光炸弹  ​​​​​​】问题。
 
#include
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    int a[n][m],sum[n][m];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    return 0;
}
 
2).差分算法 
差分算法就是基于前缀和延伸出的一种解题思想常用于解决区间需要大量修改问题。（差分在某种程度上可以看成前缀和的逆运算） 
例题：假如有一个年级考试，批卷时发现有一题全体改错了，需要全部加x分。按照朴素暴力的思想，就是将以前所有的批了的试卷全部再拿出来，再一张张的加分。这当然过于的慢，所以便有了差分的这种算法：说白了，就是将一整个考场的试卷封面上写上“加x分”，这样便省去了许多功夫。
 
#include 
using namespace std;

int main()
{
    int SIZE=10005;

    int a[SIZE],c[SIZE*10];
    int ans=0,ask,n,m,x,y,w;
    cin>>n;    //输入数列长度和修改次数
    for (int i=1; i<=n; i++)
        cin>>a[i];    //输入数列
    cin>>x>>y>>w; //从x到y全部加w
    c[x]+=w;      //x处标记+w
    c[y+1]-=w;       //y+1处标记-w
    cin>>ask;        //输入查询下标
    for (int i=1; i<=ask; i++)
   {
       ans+=c[i];
       cout<