---

---

1.题目

DP34 【模板】前缀和

描述

给定一个长度为n的数组a1,a2,…ana1,a2,…a**n.

接下来有q次查询, 每次查询有两个参数l, r.

对于每个询问, 请输出al+al+1+…+ara**l+a**l+1+…+a**r

输入描述：

第一行包含两个整数n和q.

第二行包含n个整数, 表示a1,a2,…ana1,a2,…a**n.

接下来q行,每行包含两个整数 l和r.

输出描述：

输出q行,每行代表一次查询的结果.

示例1

输入：

3 2
1 2 4
1 2
2 3

输出：

3
6

2.思路

暴力解法，时间复杂度为O(n*q)，q是查询次数，这里主要用前缀和

• ⽤ dp[i] 表⽰： [1, i] 区间内所有元素的和，那么 dp[i - 1] ⾥⾯存的就是 [1, i-1]区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i]
• 当询问的区间是 [l, r] 时：区间内所有元素的和为：dp[r] - dp[l - 1]
• 注意，下表边界从1开始，方便计数

3.代码

#include <iostream>
#include <vector>
using namespace std;int main() {//1.读取数据int n,q;cin >> n >> q;vector<int> arr(n + 1);for(int i = 1;i <= n;i++)cin >> arr[i];//2.预处理出来一个前缀和数组vector<long long> dp(n + 1);//防止溢出for(int i = 1;i <= n;i++)dp[i] = dp[i - 1] + arr[i];//3.使用dpwhile(q--){int l,r;cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;
}

---