一、定义
前缀和：是指某序列的前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
【题目描述】
有一实数序列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*
【题目描述】
设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
【输入描述】
输入：M。
【输出描述】
输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。
【样例输入】
3
【样例输出】
1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1
前言
所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。
比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。
开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。
基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
应用
（1）二分搜索
（11）一元三次方程求解
快速排序：
void qsort(int left, int right){ int i=left; j =right; mid=a[left+right]/2; while(i<=j){ while(a[i]<mid) i++; while(a[j>mid]) j--; if(i<=j){ swap(a[i],a[j]); i++; j--; } } if(left<j) qsort(left,j); if(i<right) qsort(i,right); }一元三次方程求解：
描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。
给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
输入
一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。
输出
一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。
样例输入
1.0 -5.0 -4.0 20.0
样例输出
-2.00 2.00 5.00