差分数组
1.定义
对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。
上面为专业术语，通俗点说就是前面的元素减后面的元素得到差分数组。
比如说：
首先一个数组
1 2 3 4 5 6 7
那么差分之后
1 1 1 1 1 1 1就是chafen[i]存的是num[i]−num[i−1]
2.应用
先举个例子：
现在有数组a[7]
int a[7];
a[0]=1;a[1]=2;a[2]=3;a[3]=4;a[4]=5;a[5]=6;a[6]=7;a[7]=8;如果要把a[0]-a[4]都加一，最朴素的方法就是
a[0]++;a[1]++;a[2]++;a[3]++;a[4]++;时间复杂度为O(n),打字打着都很费力。
但是如果先有一个神奇的差分数组d[7]，就可以省力得多了！
现在开一个d[7]：
int d[7];
d[0]=a[0];
for(int i=1;i<=7;i++){
d[i]=a[i]-a[i-1];
}差分数组就完成啦！
差分数组是干什么用的？
你会发现，
a[0]=d[0];
a[1]=d[1]+d[0];
a[2]=d[2]+d[1]+d[0];以此类推
这样就可以单点查询 （差分数组的前缀和即原数组）
如果现在要修改a[0]-a[4]，只需要把d[0]+1（所有的a都有d[0]的元素)，然后把d[5]-1(a[5]及以后的数字都有d[5]的元素），这样就可以实现区间修改
可能你上面一句话没看懂，那么就看一个例子。
3.例题
题目描述：一些干草堆（初始全为0），要给m次区间[li,ri]的干草堆添加一堆干草，最后求出中间高度的干草堆 的高度。
题解：
给[l,r]的区间添加干草，说明l干草堆比l−1干草堆的高度高了1，同理r比r+1的干草堆高度减少了1
然后在用前缀和求一下每堆干草堆的高度，排序出解！
#include <bits/stdc++.h>
using namespace std;
int a[1000010],n,m;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x]++,a[y+1]--;
}
for(int i=1;i<=n;i++)
a[i]+=a[i-1];
sort(a+1,a+n+1);
cout<<a[n/2+1];
}