题解报告（差分模板）

差分算法：

给定n长度的数组，有m个请求，每个请求都是在 [l,r]（l<=n;r<=n）区间内加上数c，最后输出该数组。

若用暴力法求解，需要循环m个请求，每个请求都是需要遍历数组 (r-l) 遍 ((r-l）<=n)。其中的时间复杂度为O(mn)（数据范围在10e3左右）。而运用差分算法，可以将时间复杂度降到线性即O(m+n);（数据范围可以在10e7左右）

接下来具体讲解差分算法

由此可以看出差分实际上是前缀和运算的逆运算。当需要做出在 [l,r] 区间内的元素加上c的操作时，需要做出的操作为 b[ l ]+=c，由于a数组为b数组的前缀和，所以a数组在 l 后的元素都会自动加上c。而由于是在闭区间内，大于 r 下标

的元素需要减去相应的c，来抵消前面相加的c。此时的操作为 b[ r+1] -=c; 而这一步操作的时间复杂度为O(m);

在计算好差分数组后，(在初始化b数组时，值为0) 如何得到操作后的数组a，可以有两个思路：

个人：对于b数组计算b数组中的每一个前缀和，即遍历b数组，b[i]+=b[i-1];这样子相当于得到了对于每一个下标的操作c的具体值，a数组想要得到操作后的数组，只需要和计算前缀和后的b数组对于的下标相加即可

y总：可以将a数组中的元素可以看成 [l,l] 区间内加入元素 a [ l ] 到b数组中去，先做一遍初始化。然后再做m个请求操作。最后计算b数组的每一个前缀和即可。

不管哪种方法，实现的时间复杂度为O(n),即数组的长度，最终的时间复杂度为O(n+m),为线性

注：当 l 和 r 的数值过大，并且差分后的大多数元素并没有遍历到的时候，需要用到离散化的方法。

题目：

Acwing 797.差分（模板题）

//个人方法
#include
#include
using namespace std;
const int MAXN=1e6;
int a[MAXN];
int b[MAXN];
int main()
{
    int n,m;
    cin>>n>>m;
    memset(b,0,sizeof(b));//初始化差分数组
    for(int i=1;i<=n;i++) cin>>a[i];//读入原数组
    for(int i=0;i)
    {
        int ai,bi,c;
        cin>>ai>>bi>>c;
        b[ai]+=c;
        b[bi+1]-=c;
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];//计算差分数组的前缀和，使得差分数组中的对应下标的值为相应的操作后的总值
    for(int i=1;i<=n;i++) a[i]+=b[i];//对于a数组的每一个下标读入相应的操作
    for(int i=1;i<=n;i++) cout<" ";
    return 0;
}

//y总
#include
#include
using namespace std;
const int MAXN=1e6;
int a[MAXN];
int b[MAXN];

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
    return ;
}

int main()
{
    int n,m;
    cin>>n>>m;
    memset(b,0,sizeof(b));//初始化差分数组
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];//读入原数组
        insert(i,i,a[i]);//将原数组视为在区间[i,i]中加上元素a[i]
    }
    for(int i=0;i)
    {
        int ai,bi,c;
        cin>>ai>>bi>>c;
        insert(ai,bi,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];//计算差分数组的前缀和，使得差分数组中的对应下标的值为相应的操作后的总值

    for(int i=1;i<=n;i++) cout<" ";
    return 0;
}

Acwing 2041.干草堆

该题其实也是模板题，只不过题中的原数组的全部元素默认为0，只需要得到差分数组的各个前缀和即可，由于需要从小到大排序，并且输出中间值，在操作后还需要排序。并且输出最中间的值即下标为（n/2+1）

#include
#include
#include
using namespace std;
const int MAXN=1e6+5;
int st[MAXN],d[MAXN];
int main()
{
  int n,k;
  cin>>n>>k;
  //memset(st,0,sizeof(st));
  memset(d,0,sizeof(d));
  for(int i=1;i<=k;i++)
  {
    int l,r;
    cin>>l>>r;
    d[l]++; d[r+1]--;//对于区间添加干草堆
  }
  for(int i=1;i<=n;i++) d[i]+=d[i-1];//计算前缀和
  sort(d+1,d+n+1);
  cout<2+1];//计算中间数
}

题解报告（差分模板）

相关

标签