每日一题
DP34【模板】前缀和

描述
给定一个长度为n的数组a1,a2,....an.

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


输入描述：

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

第二行包含n个整数, 表示a1,a2,....an.

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



输出描述：

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



示例1

输入：

```
3 2
1 2 4
1 2
2 3
```

输出：

```
3
6
```

解法一：前缀和

时间复杂度：O(n) + O(q)

空间复杂度：O(n)
#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];
dp[i] = dp[i - 1] + arr[i]; //统计前n个数和
}
for(int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")