浅谈前缀和（一维）

前缀和的用途

前缀和是一种常用的算法技巧，通过预处理数组来快速计算某个区间的和。它的核心思想是利用空间换时间，预先计算出数组的前缀和，从而在查询时能够快速得到结果

一维前缀和的基本思想

一维前缀和的基本思想是构建一个新的数组

b

，其中

b_i

表示原数组从第

1

个元素到第

i

个元素的和。这样，在查询某个区间

[l, r]

的和时，时间复杂度为

O(1)

求前缀和数组

前缀和数组的第

i

项就是原数组从第

1

个元素到第

i

个元素的和，用代码写出来很简单

CPP

for (int i = 1; i <= n; i++){
   b[i] = b[i - 1] + a[i];
}

b_{i-1}

是前

i-1

项的和，那么求前

i

项的和就用当前项

a_i

加上

b_{i-1}

就可以了

eg:

原数组

{a_i}=(0,1,2,3,4,5,6,7,8,9)

前缀和数组

{b_i}=(0,1,3,6,10,15,21,28,36,45)

前缀和求区间和的公式

求出了前缀和数组又怎样求一个区间的和呢？

我们假设这个区间是

[l, r]

，原数组

a=(1,2,3,4,5)

，那么前缀和数组

b=(1,3,6,10,15)

，设

l=3

，

r=5

，显而易见，区间和为

12

，那怎么用代码写出来呢？我们可以用前

5

项的和减去前

2

项的和得到区间和，这与

l

和

r

有什么关系呢？我们发现

r

就等于

5

，

l-1

就等于

2

，所以我们得出一个公式：

[l,r]

的区间和

=b_r-b_{l-1}

所以用代码写就是

CPP

int ans = b[r] - b[l - 1];//[l,r] 的区间和

一维前缀和最终代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N], l, r;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		b[i] = b[i - 1] + a[i];//求前缀和数组
	}
	scanf("%d%d", &l, &r);
	int ans = b[r] - b[l - 1];//[l,r] 的区间和
	printf("%d", ans);
	
	return 0;
}

浅谈前缀和（一维）

文章操作

前缀和的用途

一维前缀和的基本思想

求前缀和数组

前缀和求区间和的公式

一维前缀和最终代码

相关推荐

评论

浅谈前缀和（一维）