个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创前缀和(1)_【模板】前缀和_模板
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接 :
2. 题目描述 :
描述
输入描述：
输出描述：
示例1
3. 解法(前缀和) :
算法思路 :
代码展示 :
结果分析 :
1. 题目链接 :
OJ链接: 【模板】前缀和
2. 题目描述 :
描述
给定一个长度为n的数组a1,a2,....ana1,a2,....an.
接下来有q次查询, 每次查询有两个参数l, r.
对于每个询问, 请输出al+al+1+....+aral+al+1+....+ar
输入描述：
第一行包含两个整数n和q.
第二行包含n个整数, 表示a1,a2,....ana1,a2,....an.
接下来q行,每行包含两个整数 l和r.
1≤n,q≤1051≤n,q≤105
−109≤a[i]≤109−109≤a[i]≤109
1≤l≤r≤n1≤l≤r≤n
输出描述：
输出q行,每行代表一次查询的结果.
示例1
输入：
3 2 1 2 4 1 2 2 3
输出：
3 6
3. 解法(前缀和) :
算法思路 :
1. 先预处理出来一个[前缀和]数组:
用dp[i]表示: [1,i]区间内所有元素的和,那么dp[i - 1]里面存的就是[1, i - 1]区间内所有元素的和,那么: 可得递推公式: dp[i] = dp[i - 1] + arr[i];
2. 使用前缀和数组,[快速]求出[某一个区间内]所有元素的和:
当访问的区间是[l, r]时: 区间内所有元素的和为: dp[r] - dp[l - 1];
代码展示 :
#include <iostream>
#include <vector>
using namespace std;int main() {int n, q;cin >> n >> q;{vector<long long> arr(n);vector<long long> dp(n + 1);for(int i = 0; i < n; i++)cin >> arr[i];for(int i = 0; i < n; i++)dp[i + 1] = dp[i] + arr[i];while(q--){int l, r;cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;}
}1. 输入部分:
代码首先读取两个整数 n 和 q，其中 n 表示数组的大小，q 表示查询的次数。
接着，它声明了一个大小为 n 的数组 arr 用于存储输入的数据，以及一个大小为 n + 1 的数组 dp 用于存储前缀和。2. 前缀和计算 :
使用一个循环从输入中填充 arr 数组。循环运行 0 到 n - 1 的索引。
另一个循环用于填充 dp 数组，其中 dp[i + 1] 存储 arr 数组的前 i 个元素的和。这样，dp 数组的第一个元素 dp[0] 是 0，而 dp[1] 是 arr[0] 的值，以此类推。
3. 查询部分 :代码使用一个 while 循环处理查询，每次查询将读取两个整数 l 和 r，表示需要计算的区间。
它通过计算 dp[r] - dp[l - 1] 来获取从 l 到 r 的区间和。这里的 dp 数组有效地将区间和查询的复杂度降低到常数时间复杂度 O(1)。
结果分析 :
主要部分的时间复杂度
1. 输入数组 arr :代码首先读取 n 个元素到数组 arr 中，这个操作是 O(n) 的时间复杂度。
2. 计算前缀和 dp :填充前缀和数组 dp 也是一个遍历操作，复杂度为 O(n)。在该部分，程序通过对 arr 中的元素进行加法运算，计算出 dp 数组。
3. 处理查询 :代码使用一个 while 循环处理 q 次查询。对于每次查询，计算区间和的操作是 O(1)，因为它只涉及 dp 数组的两次访问和一次减法运算。
因此，对于 q 次查询，总的时间复杂度是 O(q)。
综合时间复杂度
综上所述，整个程序的时间复杂度可以表示为：O(n + q)，其中 n 是输入数组的大小，q 是查询的次数。
