铭万做网站怎么样河南做网站的公司

2025 - 03 - 09 - 第 72 篇
Author: 郑龙浩 / 仟濹
【前缀和与差分 C/C++】

洛谷 P8218 求区间和

题目描述

给定 $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$

思路

典型的的一维前缀和做法，不做具体的描述了。

我已将常规的一维前缀和笔记详细记录，具体内容可见我的博客，如下

一维前缀和算法
https://blog.csdn.net/m0_60605989/article/details/146117026?fromshare=blogdetail&sharetype=blogdetail&sharerId=146117026&sharerefer=PC&sharesource=m0_60605989&sharefrom=from_link

代码

// 洛谷P8218求区间和
// Author: 郑龙浩 / 仟濹
// Time: 2025-03-09
// 这道题是一个明显的一维前缀和
#include <bits/stdc++.h>
using namespace std;
// 列表
vector <int> arr;
// 前缀和数组
vector <int> sum;
int num, m;
// 计算区间和的函数 - 利用前缀和
int get_sum(int left, int right){int ans;// 注意判断，如果left是0,0-1 == -1,没有这个下标，不合法，应该特判if (left == 0)  return sum[right];// 正常套用公式即可ans = sum[right] - sum[left - 1];return ans;
}
int main( void ){cin >> num;arr.resize(num); // 设置 arr 原数列大小sum.resize(num); // 设置 sum 前缀和 大小// 输入数列for (int i = 0; i < num; i ++)cin >> arr[i];cin >> m;// 计算前缀和sum[0] = arr[0];for(int i = 1; i < num; i ++){sum[i] = sum[i - 1] + arr[i];}int left, right;// 输入 m 个区间，边输入边运算for (int i = 0; i < m; i ++){cin >> left >> right; // 输入的是第几个，而不是下标left -= 1; // 变为下标right -= 1; // 变为下标cout << get_sum(left, right) << endl;}return 0;
}