2025 - 03 - 09 - 第 72 篇
Author: 鄭龍浩 / 仟濹
【前綴和與差分 C/C++】

洛谷 P8218 求區間和

題目描述

給定 $n$ 個正整數組成的數列 $a_1,a_2,?,a_n$ 和 $m$ 個區間 $[l_i,r_i]$，分別求這 $m$ 個區間的區間和。

對于所有測試數據，$n,m\le 10^5,a_i\le 10^4$

輸入格式

第一行，為一個正整數 $n$ 。

第二行，為 $n$ 個正整數 $a_1,a_2,?,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;
}