简单差分

数学方法——差分

引入

首先,给出一个问题:
给出$n$个数，再给出$Q$个询问，每个询问给出$le，ri，x，$要求你在$le$到$ri$上每一个值都加上$x$，而只给你$O(n)$的时间范围，怎么办？
思考一下：

1.如果暴力，卡一下$le$和$ri$，随随便便让你$O(n^2)$ $TLE$。
2.用线段树或树状数组搞一搞,抱歉,这个复杂度是$O(Qlogn)$的,还是会$T$(虽然他们解决别的题目很NB)
3.差分,没错,就是标题，很高兴$O(n)+$常数$......$

方法

还是用上面这个题目,假如要在le和ri上全都加一个x,很显然,这个O(n)是不可避免的,既然这样,那我们考虑把$O(n×Q)$变成$O(n+Q)$.也就是说,在询问中我们不去$for$来加$x$,而是做一个标记,最后一起加上。嗯，这里暂时记住就好......
现在需要自己动笔模拟一下了！

实现

1.先另外开一个专门差分的数组(大小=题中的序列长度)

2.假如在$3$~$8$的区间上加上$5$,那我们在差分数组中的$3$位置上加上一个$5$(原因暂时不懂没关系,用笔先跟着模拟),再在$8+1$的位置上减一个$5$,如此操作完Q次。

3.假如我们只有这一次操作,开始统计答案,运用前置和的思想,$cf[i]$(差分)$=cf[i-1]+cf[i]$.
那么你会发现(如果你模拟了的话),在$3$~$8$的区间上,你已经使差分数组全部加上了$5$(推广到所有$Q$一起统计答案依旧正确)

4.再用$O(n)$的$for$把他们加到原序列之中去,输出!

看一下复杂度,果然:$O($常数$×n)$.
这个代码应该不难,所以我也就不贴了(其实这算一种思想,没有完全的板子)