一、定义

前缀和：是指某序列的前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