1️⃣题目描述
题目描述：
给定一个长度为n的数组a,a,…,a。
接下来有q次查询, 每次查询有两个参数l, r。
对于每个询问, 请输出a,a,…a。
输入描述：
第一行包含两个整数n和q。
第二行包含n个整数, 表示a,a,…,a。
接下来q行,每行包含两个整数l和r。
1≤n,q≤ 1 0 5 10^{5} 105
- 1 0 9 10^{9} 109 ≤ a[i] ≤ 1 0 9 10^{9} 109
1 ≤ l ≤ r ≤ n
输出描述：
输出q行,每行代表一次查询的结果。
示例：
2️⃣题目解析
前缀和的思想是通过提前计算和存储每个位置前的元素之和，以便在需要时能够快速获取。通过预先计算并存储前缀和，我们可以在O(1)的时间复杂度内获得任意区间内元素的和，而不需要每次都重新计算。对于前缀和问题的话总共分为两步骤：①创建一个前缀和数组；②使用前缀和数组。
状态表示：
dp[i]：表示数组从[1,i]之间所有元素的和。
状态转移方程：
dp[i] = dp[i - 1] + arr[i]
关于本题目的时间复杂度如下：
- 时间复杂度：
O(q) + O(n)。O(q)是用来查询q次询问。而O(n)用来创建前缀和数组。
3️⃣解题代码
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n,q;
cin >> n >> q;
vector<long long> arr(n + 1),dp(n + 1);
for(int i = 1;i <= n;i++)
cin >> arr[i];
for(int i = 1;i <= n;i++)
dp[i] = dp[i - 1] + arr[i];
while(q--)
{
int l, r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
最后就是代码通过啦！！！