[前缀和] P8218 【深进1.例1】求区间和 - 洛谷

P8218 【深进 1. 例 1】求区间和 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

【深进1.例1】求区间和

题目描述

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

对于所有测试数据，$n,m\le 10^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

样例输入 #1

4
4 3 2 1
2
1 4
2 3

样例输出 #1

10
5

提示

样例解释：第 $1$ 到第 $4$ 个数加起来和为 $10$。第 $2$ 个数到第 $3$ 个数加起来和为 $5$。

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

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

知识点

前缀和 

题目思路

一维前缀和 看数据量在 1e5 ，区间查询直接前缀和就能过，复杂的应该是$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
}