IT评测·应用市场-qidao123.com

标题: 前缀和 [打印本页]

作者: 勿忘初心做自己    时间: 2023-5-3 08:21
标题: 前缀和
前缀和

一、介绍

前缀,顾名思义就是一个东西前面的点缀...(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;
  2. int a[N]; //原数组a[]
  3. int s[N]; //前缀和数组s[]
  4. //根据定义 一维前缀和s[i]
  5. s[i] = a[1] + a[2] + a[3] +...+ a[i];
  6. //举例 设i=3 根据上式可得
  7. s[3] = a[1] + a[2] + a[3];
  8. //根据上面举例,可以再一步写成
  9. 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]
  5. //根据上面举例,我们可以推导出求某一区间[l,r]内的和的公式
  6.   a[l]+a[l+1]+...+a[r-1]+a[r]
  7. = 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




欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4