前缀和

前缀和

一、介绍

前缀，顾名思义就是一个东西前面的点缀...（bushi

其实打比方来说就是：假如有一字符串ABCD，那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组，对于给定的数组a=[1,2,3,4]，他的前 i 项和sum就表示数组中a[0]~a的和，具体为：
sum[0]=a[0]
sum[1]=a[0]+a[1]
......
sum=sum[0]+sum[1]+...+sum;

二、定义

定义：前缀和是指某一序列的前 n 项和。

基于前缀和的使用，我们一般把前缀和分为一维前缀和和二维前缀和。
三、一维前缀和

定义

基于一维数组的前缀和就是原数组前n个元素的和。

1. const int N = 10010;
3. int a[N]; //原数组a[]
4. int s[N]; //前缀和数组s[]
6. //根据定义 一维前缀和s[i]
7. s[i] = a[1] + a[2] + a[3] +...+ a[i];
9. //举例 设i=3 根据上式可得
10. s[3] = a[1] + a[2] + a[3];
12. //根据上面举例，可以再一步写成
13. s[i] = s[i-1] + a[i];

复制代码

需要注意的一点是：数组的下标都是从 1 开始的！！！

作用

主要作用是可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。

1. //例如求a[3]+...+a[10]之间的和，我们可以利用前缀和迅速求出：
2.   a[3]+...+a[10]
3. = (a[1]+a[2]+a[3]...+a[10]) - (a[1]+a[2])
4. = s[10] - s[2]
6. //根据上面举例,我们可以推导出求某一区间[l,r]内的和的公式
7.   a[l]+a[l+1]+...+a[r-1]+a[r]
8. = s[r] - s[l-1];

复制代码

方法

一维数组求前缀和方法
[code]int a[100],s[100];for(int i = 1; i a;        }        b[0]=0;        for(int i=1;i> l >> r;                cout