差分与前缀和是一对互逆的操作，常常用于处理区间问题，差分法是解决区间加减问题，前缀和是解决区间求和问题的常用办法。
差分法
差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间，加上相同的一个数。我们如果每个都进行加法操作的话，那么复杂度 O(nm) 是平方阶的，非常消耗时间。
如果我们采用差分法，将数组拆分，构造出一个新的拆分数组，通过对数组区间的端点进行加减操作，最后将数组和并就能完成原来的操作。
差分法的特点：
- 将对于区间的加减操作转化为对于端点的操作；
- 时间复杂度为 O(n)；
- 用于维护区间的增减但不能维护乘除；
- 差分后的序列比原来的数组序列多一个数。
差分算法解题的基本思路：b[i]=a[i]-a[i-1]，a[0]=0
- b[1]=a[1]；
- 从第 2 项到 n 项，利用 b[i]=a[i]-a[i-1]差分式；
- 对于区间端点操作加减；
- 差分还原(前缀和)。
- 注意是从1开始，从0开始还有讨论i=0 的情况，使用1的话 b[1]=a[1]-a[0]=a[1]-0;
首先假设有一个数组： a[]={1 2 3 4 5 7 2} ； 差分后： b[]={1 1 1 1 1 2 -5}
一般应用场景： 让你对区间 [l,r] 加减操作 N 次
如：从第二个元素到第五个元素每个+3 ；从第二个元素到第四个元素每个-2 ；从第一个元素到第三个元素每个+1 ；....
先演示前三个：
对于每个 [l,r] 区间的加减操作都转化为对端点 l,r+1 的操作
从第二个元素到第五个元素每个+3： 转化为：
[l]+3 并且 [r+1]-3 ，即第2个+3；第5+1个元素-3
b[]是由a[]根据公式 d[i]=a[i]-a[i-1] ，a[0]= 0 .构造的新数列（差分数列) b[]：1 1 1 1 1 2 -5 现: 1 4 1 1 1 -1 -5 (操作1)（复原操作）
然后按照 d和a数列的关系，a[i]=a[i-1]+d[i],a[i]=d[1]+d[2]+....+d[i]可以得出改变后的a:1 5 6 7 8 7 2
跟原序列对比：
1 2 3 4 5 7 2 1 5 6 7 8 7 2确实是都加上了 3。
继续操作： 从第二个元素到第四个元素每个-2 转化为：
[l]+(-2) 并且 [r+1]-(-2) ，即第2个-2；第4+1个元素+2
操作1: 1 4 1 1 1 -1 -5 现 : 1 2 1 1 3 -1 -5然后根据上次得出所改变后的a按照a[i]=a[i-1]+d[i],a[i]=d[1]+d[2]+....+d[i]得出改变后的a:1 3 4 5 8 7 2
跟原序列对比：
1 5 6 7 8 7 2 1 3 4 5 8 7 2确实是都减去2了。
注意： 不用每次都复原，只用最后一次复原即可，这里是演示为什么可以用这种转化。
直接做三次，最后还原：
从第二个元素到第五个元素每个+3;从第二个元素到第四个元素每个 -2;从第一个元素到第三个元素每个+1
a[]={1 2 3 4 5 7 2}
原序列差分后： b[]={2 2 1 0 3 -1 -5}
第一次操作后：1 4 1 1 1 -1 -5
第二次操作后：1 2 1 1 3 -1 -5
第三次操作后：2 2 1 0 3 -1 -5
所以最终差分序列变成： 2 2 1 0 3 -1 -5 -2
复原后（a[i]=a[i-1]+d[i],a[i]=d[1]+d[2]+....+d[i]）： 2 4 5 5 8 7 5 0
与原序列对比：
1 2 3 4 5 7 2 2 4 5 5 8 7 5所以还是非常方便快捷的。
差分与前缀和是逆操作，常在一起出现，但是先做差分还是先做前缀和就是两种不同的算法，做不做另一种操作也决定了算法不同，所以要根据题目分析。
大学里的树木要打药
教室外有 N 棵树（树的编号从 0~N-1），根据不同的位置和树种，学校要对其上不同的药。 因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。 对于树的药是成区间分布，比如 3 - 5 号的树靠近下水道，所以他们要用驱蚊虫的药， 20 - 26 号的树，他们排水不好，容易涝所以要给他们用点促进根系的药。 诸如此类，每种不同的药要花不同的钱。 现在已知共有 M 个这样的区间，并且给你每个区间花的钱，请问最后，这些树木花了多少药费。
输入描述:
每组输入的第一行有两个整数 N和 M。 N 代表马路的共计多少棵树，M代表区间的数目，N 和 M 之间用一个空格隔开。 接下来的 M 行每行包含三个不同的整数，用一个空格隔开，表示一个区域的起始点 L 和终止点 R 的坐标，以及花费。（1 <=L<=R<= N<= 10^6,1 <= M <= 10^5）保证花费总和不超过
int范围。输出描述:
输出包括一行，这一行只包含一个整数，所有的花费
输入样例:
500 3
150 300 4
100 200 20
470 471 19
输出样例:2662
运行限制：
1. 最大运行时间：1s 2. 最大运行内存：128M
利用b[i]=a[i]-a[i-1]差分式。
(由于这里开始时都是 0，可以用，但是用完都还是 0，所以没有意义，所以直接跳过即可。)
依次读入区间的值，然后将对于区间的操作转化为对于区间端点操作加减。 由于题目树的编号从 0~N-1，而（1 <=L<=R<= N<= 10^6）我们上述所讲操作是从1开始，所以数目整体区间要右移1位。
对于每个 [L,R] 区间的加减操作都转化为对端点 L,R+1 的操作。
差分还原(前缀和)。
代码如下：
import java.util.Scanner;
public class Main {
static int b[]=new int [100005];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n; //n层
int m; // m个区间
n = in.nextInt();
m = in.nextInt();
while(m>0)
{
m--;
int l,r,value ;
l = in.nextInt();
r = in.nextInt();
value = in.nextInt();
b[l+1]+=value;
b[r+1+1]-=value;
}
for(int i=1; i<=n; i++)
b[i]=b[i]+b[i-1];//复原操作
int sum=0;
for(int i=1;i<=n;i++)
sum+=b[i];
/*
也可以一次性搞定
int sum=a[0];
for(int i=1; i<n; i++){
a[i]=a[i]+a[i-1];
sum+=a[i]
}
*/
System.out.println(sum);
}
}前缀和
前缀和算法的应用主要也是用于处理区间内求和问题。
前缀和是指某序列的前 n 项和，可以把它理解为数学上的数列的前 n 项和。当对于某一数组区间进行多次询问，[L,r] 的和时，如果正常处理，那么我们每次都要 [l,r]。查询 N 次，那么时间复杂度也是 O(nm) 也是平方阶的。
前缀和的特点：
- 将对于区间的求和操作转化为对于端点值的减法的操作；
- 区间求和操作的时间复杂度为 O(1)；
- 数组存放时要从 1 开始；
- 前缀和数组比原来的数组序列多一个数，第 0 个
前缀和算法解题的基本思路：
- 利用 sum[i]=a[i]+sum[i-1]差分式；
- 从第 1 项到 n 项，且第 0 项无数据默认为 0；
- 对于区间求和的操作转化为端点值相减。
前缀和的一般解题过程：
首先假设有一个数组： 1 2 3 4 5 7 2 ； 前缀和后： 0 1 3 6 10 15 22 24
一般应用场景： 让你对区间 [l,r] 求和操作N次
如： 从第二个元素到第五个元素的和 ; 从第二个元素到第四个元素的和;从第一个元素到第三个元素的和 ....
演示前三个： 对于每个 [l,r] 区间的求和操作转化为区间端点的加减操作 sum[l,r] =[r]-[l-1] 从第二个元素到第五个元素的和： 转化为：[5]-[1]
那么Sum[2,5]=[5]-[1]=14 且 2+3+4+5=14 确实是相等的。
继续操作： 从第二个元素到第四个元素的和 转化为：[4]-[1]
那么Sum[2,4]=[4]-[1]=9 且 2+3+4=9
继续操作： 从第一个元素到第三个元素的和 转化为：[3]-[0]
那么Sum[1,3]=[3]-[0]=6 且 1+2+3=6 符合题意，验证结束。
大学里的树木要维护
教室外有 N 棵树，根据不同的位置和树种，学校已经对其进行了多年的维护。因为树的排 列成线性，且非常长，我们可以将它们看作一条直线给他们编号。
树的编号从 1~N 。由于已经维护了多年，每一个树都由学校的园艺人员进行了维护费用的统计。
每棵树的前期维护费用各不相同，但是由于未来需要打药，所以有些树木的维护费用太高的话，就要重新种植。由于维护费用也成区间分布，所以常常需要统一个区间里的树木的维护开销。
现在园艺人员想知道，某个区间内的树木维护开销是多少。共计 M 个区间需要查询。
输入描述:
每组输入的第一行有两个整数 N（1 <= N<= 1000000）和 M（1 <= M <= 100000）。
N 代表马路的共计多少棵树，M 代表区间的数目，N 和 M 之间用一个空格隔开。接下来的一行，包含 N 个数，分别表示每颗树的维护费用每个数之间用空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点L和终止点R的坐标。
输出描述: 输出包括M行，每一行只包含一个整数，所有的花费。
输入样例:
10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7
输出样例:24 22 17
运行限制：
1. 最大运行时间：1s 2. 最大运行内存：128M
利用sum[i]=a[i]+sum[i-1]前缀和公式在输入时求出前缀和；
依次读入区间的值，然后将对于区间的求和操作转化为对于区间端点操作加减，
sum[k]=a[1]+....+a[k];设k<n, sum[n]=a[1]+...+a[k]+....+a[n]; 求sum(a[k,n]) ---》sum(a[k,n])=sum[n]-sum[k]=a[k]-a[n-1] 即对于每个 [l,r] 区间的求和操作都转化为对端点[r]-[l-1]的操作。
代码如下:
普通算法:
import java.util.Scanner;
public class Main {
static int a[]=new int [100005];//每颗树的花费
static int sum[]=new int [100005];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n; //n层
int m; // m个区间
n = in.nextInt();
m = in.nextInt();
for(int i=1;i<=n;i++)
{
a[i]= in.nextInt();
sum[i]=a[i]+sum[i-1];//先把前缀和求出
}
//再根据sum[]对区间问题进行操作
while(m>0)
{
m--;
int l,r;
l = in.nextInt();
r = in.nextInt();
System.out.println((sum[r]-sum[l-1]));
}
}
}特殊代码:
import java.util.Scanner;
import java.util.Vector;
public class Main {
static int a[]=new int [100005];
static int sum[]=new int [100005];
static Vector ans=new Vector<Integer>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n; //n层
int m; // m个区间
n = in.nextInt();
m = in.nextInt();
for(int i=1;i<=n;i++)
{
a[i]= in.nextInt();
sum[i]=a[i]+sum[i-1];
}
while(m>0)
{
m--;
int l,r;
l = in.nextInt();
r = in.nextInt();
ans.addElement(sum[r]-sum[l-1]);
}
for(Object ab:ans){
System.out.println(ab);
}
}
}