一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

二、差分数组

首先给定一个原数组a:   a[1]、a[2]、a[3]、......

然后构造一个数组b: b[1]、b[2]、b[3]....

使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

那么根据上一节讲的，a数组就是b数组的前缀和数组。 

也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

三、功能及作用

    给区间[L,R]中每个数加上 c:  B[L] +=c， B[R+1] -=c

四、构造

考虑如何构造差分数组b：

最为直接的方法：

a[0]=0  b[1]=a[1]-a[0];  b[2]=a[2]-a[1];  b[3]=a[3]-a[2];  ......  b[n]=a[n]-a[n-1];

五、应用

【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c,  a[L+1]+c,  a[L+2]=c , ....  a[R]+c

解法一：暴力解法

用for循环，从L到R区间，时间复杂度O（n），如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

解法二：差分

始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c,  ...  a[R+2]-c, ...   a[n] -c, ...

图解过程：

b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O（1）。

如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

需求1：我们要将[1,4]范围内所有的数都加上3

规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

那么用代码表示：

while(t--){//操作次数  	cin>>x>>y>>change;//左右端点值   	cin>>c;//c是每次加减的值   	b[x]=b[x]+c;  	b[y+1]=b[y+1]-c;  }

那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

那么a[i]=a[i-1]+b[i]

六、题目

【题目描述】

输入一个长度为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

【数据范围】

1≤n,m≤100000,

1≤l≤r≤n,

−1000≤c≤1000,

−1000≤整数序列中元素的值≤1000

一、定义

前缀和：是指某序列的前n项和。可以理解成数学上上的数列的前n项和。

差分：是前缀和的逆运算。

二、前缀和的分类

可以分成一维数组的前缀和和二维 数组的前缀和

• 一维数组前缀和

    定义式：

 递推式：

• 二维数组前缀和

定义式：

递推式：

三、解决什么问题

前缀和、差分是为了解决某一类问题。比如下面这道题目：

【题目描述】

输入一个长度为n的整数序列。接下来再输入M次询问，每个询问输入一对L, R。对于每次询问，输出原序列中从第L个数到第R个数的和。

【输入描述】

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

【输出描述】

共m行，每行输出一个询问的结果。

【样例输入】

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

【样例输出】

3  6  10

【数据范围】

1≤l≤r≤n,

1≤n,m≤100000,

−1000≤数列中元素的值≤1000

【题目描述】

一个5*5的矩阵，矩阵内用0，1显示。其中，0是路，表示这个点可以走，1是墙表示这个点不可以走。

问，从给定的矩阵中从左上角到右下角最少需要走多少步？

注：题目保证有解（不存在左上角和右下角为1的情况）

【输入描述】

一个5*5的矩阵

【输出描述】

一行，表示最少要走多少步？

【样例输入】

0 1 0 0 0  0 1 0 1 0  0 0 0 0 0  0 1 1 1 0  0 0 0 1 0

【样例输出】

8

【题目描述】

给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。

数据保证 (1,1)处和 (n,m)处的数字为 0，且一定至少存在一条通路

【输入描述】

第一行包含两个整数 n 和 m。

接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

【输出描述】

输出一个整数，表示从左上角移动至右下角的最少移动次数。

【样例输入】

5 5  0 1 0 0 0  0 1 0 1 0  0 0 0 0 0  0 1 1 1 0  0 0 0 1 0

【样例输出】

8

【数据范围】

1≤n,m≤100

【题目描述】

有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000)，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。

例如，5 2 4 6 2 3 2 6，可以组成的逆序对有

（5 2），（5 4），（5 2），（5 3），（5 2），

（4 2），（4 3），（4 2），

（6 2），（6 3），（6 2），

（3 2）

共：12个

【输入描述】

共两行，第一行有一个正整数n，第二行有n个整数。

【输出描述】

只有一行为逆序对个数。

【样例输入】

8  5 2 4 6 2 3 2 6

【样例输出】

12

【题目描述】

Prince对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。

一串数列即表示一个世界的状态。

平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

【输入描述】

第一行为数列中数的个数n,第二行为n ≤ 10000个数。表示当前数列的状态。

【输出描述】

输出一个整数，表示最少需要交换几次能达到平衡状态。

【样例输入】

4  2 1 4 3

【样例输出】

2

【题目描述】

有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。

如n=5时，成为：○●○●○●○●○●

任务：编程打印出移动过程。

【输入描述】

输入n。

【输出描述】

移动过程。

【样例输入】

7

【样例输出】

step 0:ooooooo*******--  step 1:oooooo--******o*  step 2:oooooo******--o*  step 3:ooooo--*****o*o*  step 4:ooooo*****--o*o*  step 5:oooo--****o*o*o*  step 6:oooo****--o*o*o*  step 7:ooo--***o*o*o*o*  step 8:ooo*o**--*o*o*o*  step 9:o--*o**oo*o*o*o*  step10:o*o*o*--o*o*o*o*  step11:--o*o*o*o*o*o*o*