【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【牛客网刷题】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

题目描述：
给定一个长度为n的数组a₁,a₂,…,a_n。
接下来有q次查询, 每次查询有两个参数l, r。
对于每个询问, 请输出a_l,a_l+1,…a_r。

输入描述：
第一行包含两个整数n和q。
第二行包含n个整数, 表示a₁,a₂,…,a_n。
接下来q行,每行包含两个整数l和r。

1≤n,q≤$10^5$
-$10^9$ ≤ a[i] ≤ $10^9$
1 ≤ l ≤ r ≤ n

输出描述：
输出q行,每行代表一次查询的结果。

示例：

输出：
3 2
1 2 4
1 2
2 3

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
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最后就是代码通过啦！！！