一、差分一般地差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。2、定义const int N 100010; int n; //n数组长度 //定义两个一维整形数组 a为原数组b为差分数组 int f[N],diff[N]; //根据定义可知 diff[i] f[i] - f[i-1]; //以此类推 diff[1] f[1]; diff[2] f[2] - f[1]; diff[3] f[3] - f[2]; ... diff[i] f[i] - f[i-1]; //转化一下求数组b的前缀和,根据上面公式可得 diff[1]diff[2]...diff[i] f[1](f[2]-f[1])...(f[i]-f[i-1]) f[i] //由此可知原序列为差分序列的前缀和序列 f[i] diff[1]diff[2]diff[3]...diff[i];序列中每个元素与其前一个元素的差作用当我们需要对数列f的某个区间所有项进行加m操作时只需要将这个数列分解为一个差分数列diff之后对左区间边界diff[L] 项进行加m操作对右边界diff[R1]项进行减m操作最后根据拆分时的公式f[i] diff[1]diff[2]diff[3]...diff[i];f(i-1)角标 di 反过来合并即可得到我们需要的数列d。不管多少个区间如此操作皆可。diff[l]1;diff[r1] -1便可以实现上述操作且降低了时间复杂度f :3 4 1 5 6 2 7 9diff:3 1 -3 4 1 -4 5 2列如都1改变后的f[0,6]项f4 5 2 6 7 37 9diff:4 1 -3 4 1 -44 2那么例如diff[2]1;diff[4]-1f3 42 6 62 7 9diff:3 1-2 4 0-4 5 2
