A8 前缀和 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P8218 ↗

题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$ ，分别求这 $m$ 个区间的区间和。

对于所有测试数据， $n,m\le10^5,a_i\le 10^4$

输入格式

第一行，为一个正整数 $n$ 。

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足 $1\le l_i\le r_i\le n$

输出格式

共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

输入输出样例

输入 #1

plaintext

输出 #1

10
5

plaintext

对于 $100 \%$ 的数据： $1 \le n, m\le 10^5$ ， $1 \le a_i\le 10^4$

算法解析#

把每项的和加起来，然后利用相减的方式得出和的值。适用于静态的区间求和，应用面非常广泛。

时间复杂度 $O(n+m)$

Python代码实现#

n = int(input())
a = list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i - 1]
m = int(input())
for i in range(m):
    l, r = map(int, input().split())
    print(s[r] - s[l - 1])

python

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m;
int a[100005],s[100005];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }

    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r; scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
}