P8218 【深进 1. 例 1】求区间和 - 洛谷 | 计算机科学教育新生态
题目来源
洛谷
题目内容
【深进1.例1】求区间和
题目描述
给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an 和 m m m 个区间 [ l i , r i ] [l_i,r_i] [li,ri],分别求这 m m m 个区间的区间和。
对于所有测试数据, n , m ≤ 1 0 5 , a i ≤ 1 0 4 n,m\le10^5,a_i\le 10^4 n,m≤105,ai≤104
输入格式
第一行,为一个正整数 n n n 。
第二行,为 n n n 个正整数 a 1 , a 2 , ⋯ , a n a_1,a_2, \cdots ,a_n a1,a2,⋯,an
第三行,为一个正整数 m m m 。
接下来 m m m 行,每行为两个正整数 l i , r i l_i,r_i li,ri ,满足 1 ≤ l i ≤ r i ≤ n 1\le l_i\le r_i\le n 1≤li≤ri≤n
输出格式
共 m m m 行。
第 i i i 行为第 i i i 组答案的询问。
样例 #1
样例输入 #1
4
4 3 2 1
2
1 4
2 3
样例输出 #1
10
5
提示
样例解释:第 1 1 1 到第 4 4 4 个数加起来和为 10 10 10。第 2 2 2 个数到第 3 3 3 个数加起来和为 5 5 5。
对于 50 % 50 \% 50% 的数据: n , m ≤ 1000 n,m\le 1000 n,m≤1000;
对于 100 % 100 \% 100% 的数据: 1 ≤ n , m ≤ 1 0 5 1 \le n, m\le 10^5 1≤n,m≤105, 1 ≤ a i ≤ 1 0 4 1 \le a_i\le 10^4 1≤ai≤104
知识点
前缀和
题目思路
一维前缀和 看数据量在 1e5 ,区间查询直接前缀和就能过,复杂的应该是 O ( n + m ) O(n + m) O(n+m)
AC代码
//
// Created by Jisam on 28/09/2024 11:53 PM.
// Solution of 求区间和
// 2024-09-28 23:58:12 AC 100 前缀和
#include <bits/stdc++.h>
#define int long long
using namespace std;
// 定义一个常量MAXN,用于限定数组的最大大小
const int MAXN = 1e5 + 5;
// 定义数组a,用于存储原始输入的整数序列
int a[MAXN];
// 定义数组b,用于存储a数组的前缀和,即b[i]表示从a[1]到a[i]的累加和
int b[MAXN];
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
// 读取整数n,表示原始序列的长度
int n;
cin >> n;
// 读取并计算原始序列a的前缀和,存储在数组b中
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i] + b[i - 1];
}
// 读取整数m,表示需要查询的区间数量
int m;
cin >> m;
// 处理m次区间查询
for (int i = 0; i < m; i++) {
// 读取区间端点x和y,表示查询从x到y的区间和
int x, y;
cin >> x >> y;
// 根据前缀和数组b,计算并输出区间[x, y]的和
cout << b[y] - b[x - 1] << "\n";
}
return 0
}