前缀和用于各种数组求和问题,对比暴力解法可有效降低时间复杂度

原题复现

https://www.luogu.com.cn/problem/P8218

题目描述

给定由 nn 个正整数组成的序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 和 mm 个区间 [li,ri][l_i,r_i]，分别求这 mm 个区间的区间和。

输入格式

第一行包含一个正整数 nn，表示序列的长度。

第二行包含 nn 个正整数 a1,a2,⋯ ,ana_1,a_2, \cdots ,a_n。

第三行包含一个正整数 mm，表示区间的数量。

接下来 mm 行，每行包含两个正整数 li,ril_i,r_i，满足 1≤li≤ri≤n1\le l_i\le r_i\le n。

输出格式

共 mm 行，其中第 ii 行包含一个正整数，表示第 ii 组答案的询问。

输入输出样例 #1

输入 #1

1
2
3
4
5
4
4 3 2 1
2
1 4
2 3

输出 #1

1
2
10
5

说明/提示

样例解释

第 11 到第 44 个数加起来和为 1010。第 22 个数到第 33 个数加起来和为 55。

数据范围

对于 50%50 \% 的数据：n,m≤1000n,m\le 1000；

对于 100%100 \% 的数据：1≤n,m≤1051 \le n, m\le 10^5，1≤ai≤1041 \le a_i\le 10^4。

解题思路

看上去只是复杂点的a+b problem?但直接暴力求解面对10510^5数量级的数据时必然会TLE

优化方式是在预处理中求出前缀和,查询时对应位置的前缀和作差即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys

n = int(input())
data = list(map(int,input().split()))
m = int(input())
op = list(sys.stdin.readlines())
res = []
presum = [0]*(n+1)

for i in range(n):
    presum[i+1] = presum[i] + data[i]

for i in op:
    s = 0
    i = i.strip()
    bg,ed = map(int,i.split())
    res.append(presum[ed] - presum[bg-1])

for i in res:
    print(i)

时间复杂度:预处理O(n),查询O(1)
空间复杂度:O(n)
轻松AC喵~