差分——（1）一维差分

差分，是一种和前缀和相对的策略。

差分概念

对于一个数列 ，我们需要维护的数据是“相邻两个数之差”。这种策略是，令，即相邻两数的差。我们称数列 为数列 的差分数列。

应用

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。譬如使 [l, r] 每个数加上一个 k，就是 ，最后做一遍前缀和。

就是对这个差分数列 做一遍前缀和就得到了原来的数列 ，即 相当于 这个前缀和。

证明如下：

这样，我们可以发现一个规律，即第二个多项式的系数为 i-1。我们用 来维护这个数组，那么 ，并且在修改时候维护 数组，即 只后便有了公式 。

举例

目前 ，则对应的差分数列 。

给 [3, 5] 加上首项为2、公差为 1 的等差数列，及 。那么原数列变为 ，对差分数列变为 。

说明 a 区间加等差，相当于 p 区间加常数、端点单点修改。也就是区间加自然是给 加上 d。

模板题

题目链接

我的OJ，http://47.110.135.197/problem.php?id=5226。

题目描述

输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l,  r,  c，表示将序列中 [l, r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。

输入

第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数序列。
接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出

共一行，包含 n 个整数，表示最终序列。

样例输入

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

样例输出

3 4 5 3 4 2

分析

这是一个一维差分的模板题。

数据分析

下面我们根据样例输入来分析一下，样例输出是如何得到的。

初始状态的差分数组 diff 为 1 1 0 -1 1 -1。注意第一个下标为 1。

第一次操作为 1 3 1，那么就是 diff[1] = diff[1]+1，diff[4] = diff[4]-1，得到差分数组 diff 变为 2 1 0 -2 1 -1。

第二次操作为 3 5 1，那么就是 diff[3] = diff[3]+1，diff[6] = diff[6]-1，得到差分数组 diff 变为 2 1 1 -2 1 -2。

第三次操作为 1 6 1，那么就是 diff[1] = diff[1]+1，diff[7] = diff[7]-1，得到差分数组 diff 变为 3 1 1 -2 1 -2 -1。

因此，最终的原始数组如下：

a[1] = diff[0]+diff[1] = 3

a[2] = diff[0]+diff[1]+diff[2]  = 4

a[3] = diff[0]+diff[1]+diff[2]+diff[3]  = 5

a[4] = diff[0]+diff[1]+diff[2]+diff[3]+diff[4]  = 3

a[5] = diff[0]+diff[1]+diff[2]+diff[3]+diff[4]+diff[5]  = 4

a[6] = diff[0]+diff[1]+diff[2]+diff[3]+diff[4]+diff[5]+diff[6]  = 2

数据范围

从题目中知道，n 的最大值为 100000，因此我们定义数组为 100004。

数组的每个数范围为 [-1000, 1000]，c 的范围为 [-1000, 1000]，操作数 m 最大值为 100000。因此我们可以计算出，经过 m 次操作后，最大的数据为 1000+1000*100000 = 10^8+1000，在 int 的表示范围内。同理最小的数据将是 -1000+(-1000*100000)=-10^8-1000，也在 int 的表示范围内。

AC代码

#include 
using namespace std;const int MAXN = 1e5+6;
int data[MAXN] = {};
int diff[MAXN] = {};int main() {int n,m;scanf("%d%d", &n, &m);int i;for (i=1; i<=n; i++) {scanf("%d", &data[i]);diff[i] = data[i] - data[i-1];}for (i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！