这是ccf2022年3月份的第二题出行计划，用到了差分算法，我不明白用差分算法的原理是什么，虽然我已经了解了差分算法却依然不理解代码，我把一个博主的满分代码放在下面了

Question

这是ccf2022年3月份的第二题出行计划，用到了差分算法，我不明白用差分算法的原理是什么，虽然我已经了解了差分算法却依然看不理解代码，我把一个博主的满分代码放在下面了，希望有人可以给我讲讲

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e5+10;
int n,m,k;
int b[N];//差分数组
//令l～r之间的数都+c
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        int left = x-y+1;//定义左边界
        left = left>0?left:1;
        int right = x;//定义右边界
        insert(left,right,1);
    }
    //前缀和操作，得到各个点的数值
    for(int i=1;i<=N;i++)
    {
        b[i] = b[i-1]+b[i];
    }
    while(m--)
    {
        int x;
        cin>>x;
        cout<<b[x+k]<<endl;//直接得到x+k处的数值
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「只须一笑不须愁X」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_53641110/article/details/124031629

Answer 1

可参考

差分法~超详细（公式+原理+例题）_Blind-Stab的博客-CSDN博客_差分法 差分法差分法应用在处理区间问题时比较多。一个数列要在很多不确定的区间内加上相同的一个数，如果直接在原数列上操作是非常复杂且耗时的，差分法就是先将数列拆分，构造一个拆分的新数列，在这个新数列上进行我们想要的操作之后，在将这个数列合并起来即可。听起来好像复杂了很多，其实不然，这样处理反而能减少很多操作，比如不用对给定区间内的原数列的每一项进行操作，只需要在新数列上操作区间左右边界的这两项即可，这样就达到了减少耗时的效果。定义：对于已知有n个元素得离线数列d，我们可以建立记录它与每项与前一项得差值 https://blog.csdn.net/qq_41054844/article/details/111592532