每日算法练习Day04

B3612 【深进1.例1】求区间和

题目来源：https://www.luogu.com.cn/problem/B3612#ide

题目描述

给定nnn个正整数组成的数列a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​和mmm个区间[li,ri][l_i,r_i][li​,ri​]，分别求这mmm个区间的区间和。

输入格式

第一行包含一个正整数nnn，表示序列的长度。

第二行包含nnn个正整数a1,a2,⋯ ,ana_1,a_2, \cdots ,a_na1​,a2​,⋯,an​。

第三行包含一个正整数mmm，表示区间的数量。

接下来mmm行，每行包含两个正整数li,ril_i,r_ili​,ri​，满足1≤li≤ri≤n1\le l_i\le r_i\le n1≤li​≤ri​≤n。

输出格式

共mmm行，其中第iii行包含一个正整数，表示第iii组答案的询问。

输入输出样例 #1

输入 #1

4 4 3 2 1 2 1 4 2 3

输出 #1

10 5

说明/提示

样例解释

第111到第444个数加起来和为101010。第222个数到第333个数加起来和为555。

数据范围

对于50%50 \%50%的数据：n,m≤1000n,m\le 1000n,m≤1000；

对于100%100 \%100%的数据：1≤n,m≤1051 \le n, m\le 10^51≤n,m≤105，1≤ai≤1041 \le a_i\le 10^41≤ai​≤104。

题解

importjava.util.Scanner;// 1. 导入扫描器类，用于读取控制台输入publicclassMain{// 2. 定义主类，Java程序入口，类名需和文件名一致publicstaticvoidmain(String[]args){// 3. 主方法，程序执行的入口Scannersc=newScanner(System.in);// 4. 创建Scanner对象，关联控制台输入流intn=sc.nextInt();// 5. 读取第一个整数n：表示原数组的元素个数// 6. 定义原数组a和前缀和数组s，长度n+1（索引0闲置，1~n存数据，和C++1-based索引一致）int[]a=newint[n+1];int[]s=newint[n+1];// 7. 循环读取n个元素，构建原数组a + 前缀和数组s（核心预处理）for(inti=1;i<=n;i++){a[i]=sc.nextInt();// 8. 读取第i个整数，存入原数组a的第i位s[i]=s[i-1]+a[i];// 9. 前缀和核心公式：s[i] = 前i个元素的累加和}intm=sc.nextInt();// 10. 读取整数m：表示后续的区间和查询次数// 11. 循环处理m次查询，每次O(1)时间出结果for(inti=1;i<=m;i++){intl=sc.nextInt();// 12. 读取查询的左边界lintr=sc.nextInt();// 13. 读取查询的右边界r// 14. 区间和核心计算：[l,r]的和 = 前r项和 - 前l-1项和，直接打印结果System.out.println(s[r]-s[l-1]);}sc.close();// 15. 关闭Scanner，释放输入流资源}}

这个是关于前缀和的问题，先设置好前缀和的数组，然后通过for循环来得到每一个前缀和，得到一个前缀和数组。
然后读取输入的l和r,通过循环可以获得多组l和r的相减的结果。然后输出就可以了。
要注意到边界条件，l不能小于1