csp信奥赛C++高频考点专项训练之前缀和差分 --【一维前缀和】：求区间和
csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维前缀和】：求区间和
题目描述
给定由n nn个正整数组成的序列a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1,a2,⋯,an和m mm个区间[ l i , r i ] [l_i,r_i][li,ri]，分别求这m mm个区间的区间和。
输入格式
第一行包含一个正整数n nn，表示序列的长度。
第二行包含n nn个正整数a 1 , a 2 , ⋯ , a n a_1,a_2, \cdots ,a_na1,a2,⋯,an。
第三行包含一个正整数m mm，表示区间的数量。
接下来m mm行，每行包含两个正整数l i , r i l_i,r_ili,ri，满足1 ≤ l i ≤ r i ≤ n 1\le l_i\le r_i\le n1≤li≤ri≤n。
输出格式
共m mm行，其中第i ii行包含一个正整数，表示第i ii组答案的询问。
输入输出样例 1
输入 1
4 4 3 2 1 2 1 4 2 3输出 1
10 5说明/提示
样例解释
第1 11到第4 44个数加起来和为10 1010。第2 22个数到第3 33个数加起来和为5 55。
数据范围
对于50 % 50 \%50%的数据：n , m ≤ 1000 n,m\le 1000n,m≤1000；
对于100 % 100 \%100%的数据：1 ≤ n , m ≤ 10 5 1 \le n, m\le 10^51≤n,m≤105，1 ≤ a i ≤ 10 4 1 \le a_i\le 10^41≤ai≤104。
思路分析
本题要求多次查询区间和，最朴素的做法是每次从l到r累加，但最坏复杂度 O(n*m) 会超时（n,m ≤ 1e5）。
使用前缀和优化：预处理前缀和数组s，其中s[i] = a[1] + a[2] + ... + a[i]，则区间[l, r]的和 =s[r] - s[l-1]。
预处理 O(n)，每次查询 O(1)，总复杂度 O(n+m)，满足要求。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,m,l,r,a[100010],s[100010];// a存原序列，s存前缀和intmain(){cin>>n;// 读入长度for(inti=1;i<=n;i++){cin>>a[i];// 读入每个数s[i]=s[i-1]+a[i];// 计算前缀和，s[0]=0}cin>>m;// 读入查询次数while(m--){cin>>l>>r;// 读入区间端点cout<<s[r]-s[l-1]<<'\n';// 区间和 = 前缀和相减}return0;}功能分析
- 输入处理：读取序列长度 n，随后依次读取 n 个整数，同时在读取过程中动态构建前缀和数组
s，使得s[i]保存前 i 个元素的和。 - 查询处理：读取查询次数 m，对每组
[l, r]，利用前缀和公式s[r] - s[l-1]直接计算出区间和，并输出结果。 - 性能：时间复杂度 O(n+m)，空间复杂度 O(n)，能够通过 100% 的数据（n,m ≤ 1e5）。
【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}