前缀和这东西吧，总会以各种奇形怪状的样子出现在我们面前。比如H1017子问题，H1018小图的棋盘

众所周知一维前缀和的构造公式是:

$s[i]=s[i-1]+a[i]$

二维前缀和的是:

$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$

而且前缀和还有一个形式独特的逆运算：

差分~~~~~

一维差分的构造公式为：

$s[i]=a[i]-a[i-1]$

差分有两个个特点，原数组的差分数组的前缀和数组就是原数组，列个表一看：

下标	1	2	3	4	5
原数组	1	3	6	4	5
原数组的差分数组		2	3	-2	1
差分数组的前缀和数组		3	6	4	5

第二点：对于一个有$n$项的数组，如果在差分数组的第$i$项加$k$（减法同理），那么将差分数组通过前缀和还原成原数组时，原数组的第$i$~$n$项全都加$k$

比如如果我们在差分数组的第3项加1，就相当于在原数组的第3~$n$项加1

而差分的这两个独特特征使它可以做到在一个区间内快速加上一个数

比如如果我们要在上面数组里的第2~4位加3，就可以在其差分数组第2位加3，再在第5位减3

因为在差分数组第2位加3相当于在原数组第2~5位加3，但是第5位被多余加了3，所以还得在第五位减三

顺带提一下二维差分：

$s[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

现在看看这道题：

给定一个长为n的数组，有k次询问，每次输入$l_i$和$r_i$表示在数组$[l_i,r_i]$的范围里加一，最后输出这个数组

样例： 输入：

5 3 1 2 4 5 2 4

输出：

1 2 2 2 1

请先自己打出来符合要求的代码，再继续看

答案：

```c++
#include<iostream>
using namespace std;
int a[100001],s[100001];
int main(){
   int n,k,l,r;
   cin>>n>>k;
   for(int i=1;i<=k;i++){
        cin>>l>>r;
        s[l]++;
        s[r+1]--;
   }
   for(int i=1;i<=n;i++){
        a[i]=a[i-1]+s[i];
        cout<<a[i]<<" ";
   }
}

前缀和和差分准确来说是一种思想，没有定型，它们的适用范围就是区间，有兴趣的可以去洛谷看看以下几个题：

P8649

CF1722E

P2280

P1387

P2367

P7404