有趣的差分，区间修改的优化选择
做数组题的时候，可能会多次去改变某一区间元素的值，多重利用循环效率过差，这里我们来了解一下差分，复杂度为O(1)
什么是差分？
差分就是，数组中每一项减去它前一项的差值，该差值作为差分数组。 eg:序列1 6 5 8 7 3 差分序列：1 5 -1 3 -1 -4
公式：b[i] = a[i] - a[i-1]
代码实现：
#include<iostream>
using namespace std;
int a[7]={0,1,6,5,8,7,3};
int b[7];
int main()
{
for(int i=1;i<=6;i++)
{
cout<<a[i]<<" ";
b[i]=a[i]-a[i-1];//每一项分别与前一项做差
}
cout<<endl;
for(int i=1;i<=6;i++)
cout<<b[i]<<" "; //输出差分序列
cout<<endl;
return 0;
}
看到这里是否会有些疑惑，我们得到的差分序列到底有什么用？往下看，你会感到惊喜的！
差分序列的性质和应用(重点)
- 差分序列求前缀和还原成原序列：代码实现：
公式：b[i] = b[i] + b[i-1]
for(int i=1;i<=6;i++)
{
b[i]=b[i]+b[i-1];//差分序列求前缀和,得到原序列
cout<<b[i]<<" ";
}
- 区间修改：这是差分最神奇的地方！还是上面的例子： 序列 1 6 5 8 7 3 差分序列：1 5 -1 3 -1 -4 将区间 [1,3] 的元素全部加1，得到：序列2 7 6 8 7 3 差分序列：2 5 -1 2 -1 -4 对比两个差分序列，我们会发现，在对区间[1,3] 进行处理的时候，差分序列只有 1和4 发生了相应的改变。其实这并不是特例，而是一个经得起推敲的结论。因为在对区间[1,3]的元素进行相应的+1操作后，a1+1, a2+1, a3+1, a4, a5, a6...,我们再进行求差分：a1+1-(a0=0), a2-a1, a3-a2, a4-a3-1, a5-a4, a6-a5,我们就可以直观的看出，其实当原序列进行区间统一改变时，对于差分序列而言受影响的只有对应区间的第一个元素，和最后一个元素的下一位,即b[l]+1,b[r+1]-1
公式：当区间[l,r]内所有元素+c的时候，对应的差分序列：b[l]=b[l]+c, b[r]=b[r+1]-c
再经过前缀求和就可得到，进行区间[l,r]改变后的序列:
int L,R; //序列a的区间[L,R]中的全部元素+1
cin>>L>>R;
b[L]+=1; //对应的分差序列的，b[L]+1,b[R+1]-1
b[R+1]-=1;
for(int i=1;i<=6;i++)
{
b[i]=b[i]+b[i-1];
cout<<b[i]<<" ";
}
- 对应真题：传送门
题目描述 天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的：一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。输入描述: 第一行输入两个数 n (1≤n≤2×105) 和 m (1≤m≤2×105) 。接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第 r 个的和。输出描述: 输出一个整数，代表他们队伍总分的最大值。示例1 输入 复制 7 3 1 3 3 7 5 6 输出 复制 46 说明 一个符合条件的排列是 [1,3, 6, 4, 7, 5, 2]，于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
int n,m,l,r;
int a[maxn];
long long sum=0;
int main()
{
cin>>n>>m;
while(m--)
{
cin>>l>>r;
a[l]+=1;
a[r+1]-=1;
}
for(int i=1;i<=n;i++)
{
a[i]=a[i]+a[i-1]; //利用差分数组求出现的次数
}
sort(a+1,a+1+n);
int k=n;
for(int i=n;i>=1;i--)
{
sum+=a[i]*(k--);
}
cout<<sum<<endl;
return 0;
}