一、知识点 差分数组： 1、定义：某一数组的前一项-后一项的查，即差分数组da[i]=stu[i]-stu[i-1] (i>0),stu[0]=0; 2、作用范围：只能是区间元素同时增加或减少相同的数的情况才能用 3、作用：数组连续区间同时增或者同时减时，避免区间修改的数据量大时导致超时 4、例子：在a和b区间同时增加c，则da[a]+=c;da[b+1]-=c; 之后stu[i]=da[1]+da[2]+…+da[i] (i>0) 二、例题 1、分苹果 2、代码
#include<stdio.h> #include<string.h> int da[100005]; int main(){ int a,b,c; int i,j; int n,m; int sum=0; memset(da,0,sizeof(da)); scanf("%d %d",&n,&m); for(i=1;i<=m;i++){ scanf("%d %d %d",&a,&b,&c); da[a]+=c; da[b+1]-=c; } sum+=da[1]; printf("%d",sum); for(i=2;i<=n;i++){ sum+=da[i]; printf(" %d",sum); } return 0; }参考资料 差分数组
