题意整理。

• 给定一个长度为n的数组。
• 有q次查询，每次查询给定左右边界l和r，输出下标在l、r之间的所有元素的累加和。

方法一（前缀和）

1.解题思路

• 首先对数组进行预处理，得到对应的前缀和数组。
• 利用前缀和数组r下标对应的值减去l-1下标对应的值，即可得到下标在l、r之间的所有元素的累加和。

图解展示：

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        //存放数组元素
        int[] arr=new int[n];
        //存放前缀和
        long[] presum=new long[n+1];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
            presum[i+1]=presum[i]+arr[i];
        }
        //q次查询
        while(q-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            //输出查询结果
            System.out.println(presum[r]-presum[l-1]);
        }
    }
}

3.复杂度分析

• 时间复杂度：需要遍历数组中所有元素构建前缀和数组，预处理的时间复杂度为$O(n)O(n)$，每次查询只需进行一次运算，所以查询的时间复杂度为$O(1)O(1)$。
• 空间复杂度：需要额外长度为$n+1n+1$的前缀和数组，所以空间复杂度为$O(n)O(n)$。