题解 | #【模板】前缀和#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int q = in.nextInt();
            int[] arr=new int[n+1];//目标数组,因为下标从1开始,所以多给1
            int index=1;//获取输入值的下标
            while(index<n+1){//获取,从1开始,那么结尾也就自然到了n
                arr[index++]=in.nextInt();
            }
            long[] db=new long[n+1];//前缀和数组,因为默认是0,所以第一个不用处理-->因为有累加和的存在,怕值太大
            index=1;//遍历,求前缀和,从1下标开始
            while(index<n+1){
                db[index]=db[index-1]+arr[index];//所以第一个元素就是0+arr[1]了
                index++;
            }
            //现在有了数组,和数组长度,及其要查询的次数q,及前缀和数组db
            //现在开始处理q次查询了
            while(q>0){//只有--到1的时候,再--一次到0才会出循环
                int l=in.nextInt();
                int r=in.nextInt();
                System.out.println(db[r] - db[l-1]);//输出区间和即可
                q--;//次数--
            }
        }
    }
}

暴力解法：

每一次都求对应区间的和即可，时间复杂度O(N*q)

前缀和：

能快速求出数组中某一个区间的和，这个就是前缀和的作用，与题意符合，所以可以使用

步骤：我们下面的数组下标都从1开始的，不从0开始，原因后面讲

1，预处理出来一个前缀和数组：dp[]

这个数组满足

1.1--->dp[i]表示arr数组中的前i个下标元素的和

如：dp[4]表示arr数组中的前第1,2,3,4个下标的元素和

1.2--->dp[i]=dp[i-1]+arr[i]

2，使用前缀和数组dp[ ]

我们要求的[L,R]的所有元素和：可以用dp[R]-dp[L-1]来表示，直接找到对应下标相减即可

===》现在问题就来了，为什么我们的下标要从1开始，

如果我们从0开始的话dp[L-1]=dp[0-1]=dp[-1]，那不就越界了吗，所以不是从0开始的下标

若是题目要求下标从0开始的话，我们可以把这种情况单独拎出来，if(L-1==-1)，为dp[0]=0;

[0,R]直接就是dp[R]了不用减一个数了