差分数组（超详细）

先从一到题入手：

数列游戏：

给定一个长度为n的序列：

首先进行x次操作，没下次操作在Li和Ri这个区间加上一个数Ci

然后进行y次询问，每次询问Li到Ri的区间和。

初始序列都为0。

（数据较大）

这明显是一道线段树裸题！

但有没有其他更加简便的解法？

差分数组！！！

差分数组：

对于一个数组A，其差分数组且。

令（SumD是差分数组D的前缀和）

则

即A[i]的差分数组是D[i]，而D[i]的前缀和是A[i]

对于“数列游戏”这道题：
如果每次都修改从L到R的值的话，一定会TLE。

注意特殊处：这道题先是进行区间修改，最后再同意查询。

所以，我们只要维护一个差分数组就行了。

维护差分数组，队医区间[L, R]加C，我们只需要将D[L] + C和D[R+1]-C

当修改完毕后，我们先求一遍差分前缀和就得到了修改后的数组A，

然后对A求一遍前缀和，这样每次查询的时候这要计算一次就可以得到结果了。

参考代码：

cin >> n >> x >> y;
for(int i = 1; i <= x; i ++){
    cin >> l >> r >> c;
    D[L] = D[L] + C;
    D[R + 1] = (D[R + 1] - C);
}
for(int i = 1; i <= n; i ++) A[i] = (D[i] + A[i - 1]);
for(int i = 1; i <= n; i ++) SumA[i] = SumA[i - 1] + A[i];
for(int i = 1; i <= n; i ++){
    cin >> l >> r;
    cout << SumA[l] - SumA[L - 1] << "\n";
}

今天的差分数组就结束了，希望你们有收获！