前缀和
一、介绍
前缀,顾名思义就是一个东西前面的点缀...(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个元素的和。
- const int N = 10010;
-
- int a[N]; //原数组a[]
- int s[N]; //前缀和数组s[]
-
- //根据定义 一维前缀和s[i]
- s[i] = a[1] + a[2] + a[3] +...+ a[i];
-
- //举例 设i=3 根据上式可得
- s[3] = a[1] + a[2] + a[3];
-
- //根据上面举例,可以再一步写成
- s[i] = s[i-1] + a[i];
复制代码 需要注意的一点是:数组的下标都是从 1 开始的!!!
作用
主要作用是可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。
- //例如求a[3]+...+a[10]之间的和,我们可以利用前缀和迅速求出:
- a[3]+...+a[10]
- = (a[1]+a[2]+a[3]...+a[10]) - (a[1]+a[2])
- = s[10] - s[2]
-
- //根据上面举例,我们可以推导出求某一区间[l,r]内的和的公式
- a[l]+a[l+1]+...+a[r-1]+a[r]
- = 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 |