一、定义

前缀和：是指某序列的前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;  }

(adsbygoogle = window.adsbygoogle || []).push({});