差分介绍

设数组 data[]={1,6,8,5,10},那么差分数组 different[]={1,5,2,-3,5} 也就是说 different[i]=data[i]-data[i-1] (data[0]=0);

那么 data[i]=${\sum }_{down=1}^{i}b[down]\frac{}{}$

假如区间[2,4]都加上2的话 此时 data[]={1,8,10,7,10}; different[]={1,7,2,-3,3}

发现 different 数组只有different[2]和different[5]变了，因为区间[2,4]是同时加上2的，所以区间内 different[i]~different[i-1]是不变的

当我们对一个区间[x,y]进行修改的时候，只需要对它的差分数组进行修改，只需要修改 different[x]和different[y+1];

different[x]+=k;different[x]-=k;

例题

由于巨人们的进攻，人类的生活圈已经越来越小。某一年，巨人又开始对南方的围墙发起猛攻，但是南方围墙非常坚固，巨人无法攻进去。不过巨人在某一天感染了一种特殊病毒，这种病毒可以让巨人长高。长高的巨人就可以突破围墙了，这令南方的守城兵长非常恐慌，他不断派人把围墙修改以抵挡敌人的进攻。最后巨人终于停止了这一波攻击。士兵长想知道现在每一堵墙有多高。

输入 第一行两个数n，m表示有n堵围墙，m次修墙

接下来一行n个数为围墙的初始高度。

接下来m行每行3个数Li,Ri，Xi，表示第Li到Ri堵围墙都增高Xi米

输出 一行n个数：第i个数表示编号为i的墙的最后高度。

样例输入 5 2 1 2 3 4 5 1 5 1 2 4 1 样例输出 2 4 5 6 6 【数据范围】 对于30%的数据：1 ≤ n、m ≤ 1000。

对于60%的数据：1 ≤ n、m ≤ 100000。

对于100%的数据：1 ≤ n、m ≤ 700000，1 ≤ Li ≤ Ri ≤ n，1 ≤ Xi ≤ 1000。

#include<cstdio> #include<iostream> using namespace std; typedef unsigned long long ull; #define digit 700001 ull data[digit],record[digit]; ull length,times; void enter() { record[0]=0; record[length+1]=0; scanf("%lld%lld",&length,×); for(ull i=1;i<=length;i++) scanf("%lld",&data[i]), record[i]=data[i]-data[i-1]; ull x,y,addsum; while(times--) { scanf("%lld%lld%lld",&x,&y,&addsum); record[x]+=addsum; record[y+1]-=addsum; } ull sum=0; for(ull i=1;i<=length;i++) { sum+=record[i]; printf("%lld ",sum); } } int main() { enter(); return 0; }

小结

以后对于区间内加减法并要求输出的题都可以考虑一下 差分算法

关于

感谢 Lyp10000