一、定义

前缀和：是指某序列的前n项和。可以理解成数学上上的数列的前n项和。

差分：是前缀和的逆运算。

二、前缀和的分类

可以分成一维数组的前缀和和二维 数组的前缀和

• 一维数组前缀和

    定义式：

 递推式：

• 二维数组前缀和

定义式：

递推式：

三、解决什么问题

前缀和、差分是为了解决某一类问题。比如下面这道题目：

【题目描述】

输入一个长度为n的整数序列。接下来再输入M次询问，每个询问输入一对L, R。对于每次询问，输出原序列中从第L个数到第R个数的和。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

【输出描述】

共m行，每行输出一个询问的结果。

【样例输入】

5 3
2 1 3 6 4
1 2
1 3
2 4

【样例输出】

3
6
10

【数据范围】

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

看到这个题目可能很多人会想到暴力求解方法，比如下面这样：

#include<iostream>
using namespace std;
int main(){
    int n,m,sum=0;
    int a[100]; 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //暴力求解
    while(m--){
        int L,R;
        int sum=0;
        cin>>L>>R;
        for(int i=L;i<=R;i++){
            sum+=a[i];
        }
        cout<<"sum="<<sum<<endl;  
    }
  
    return 0;
}

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

 核心代码：

for (int i = 1; i <= n; i ++ ){
	cin >> a[i];
	s[i] = s[i - 1] + a[i];
}

特别是s[i]=s[i-1]+a[i]这行代码，这行代码拆解如下：

s[1]=s[0]+a[1]; //s[0]为0
s[2]=s[1]+a[2]=a[1]+a[2];
s[3]=s[2]+a[3]=a[1]+a[2]+a[3];
s[4]=s[3]+a[4]=a[1]+a[2]+a[3]+a[4];
......

按照上面这样，我们就能得到前缀和了。

我们这么做的优势在于：以O(1)的时间复杂度得到某块区间的总和。

那么，我们求区间和的过程就相对简单了。

因为L<=R, 所以我们可以参考下面的过程：

s[L]=a[1]+a[2]+a[3]+....+a[L]

s[R]=a[1]+a[2]+a[3]+...+a[L]+a[L+1]+a[L+2]+....+a[R]

我们要求的是a[L]+a[L+1]+...+a[R]。也就是s[R]-s[L-1];

然后我们的代码就可以参考下面这样写：

#include<iostream>
using namespace std;
int main(){
    int n,m;
    int a[100]={0};
	int s[100]={0}; 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    //前缀和 
   	 while (m--){
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}