区间加
Perfonster · · 个人记录
Q：给定一个数组a，执行n次操作：
求执行操作完后的数组a。
这个问题是在区间[l,r]执行“批量操作”，称为区间加。
若用for循环，时间效率较低，不提倡。
A：
设函数
规定a[0]=0，则（2）即某个数-前一个数。
显然，执行一次区间加后，区间内的数比区间外的数多k，这个状态起点是a[l]处，终点是a[r]处，则a[l]比a[l-1]多了k，a[r+1]比a[r]少了k，即执行每一次区间加操作等于执行下列2个操作：
这样，我们通过一个数比前一个数多还是少还是不多不少，判断区间加是否开始或结束。计算完每一个f'(x)值后，就可以通过a[0]=1,a[x]=a[x-1]+f'(x)，计算出a数组所有值。这个区间加的算法，时间效率高。简单说，就是：
- 根据l,r,k求增量函数在每一个x处的值
- 根据增量函数及初始值反推回原来的数组的每个值
例题：LG P1083 借教室