1.思路

这题是求给定区间的和，这里就是一维前缀和的典型模板。我们可以先创建一个n+1大小的数组，如果有必要可以再创建一个前缀和数组，而我们这里直接用的原数组当作前缀和数组。a[i] = in.nextInt() + a[i - 1];就完成了从原数组转换为前缀和数组，a[i]就代表从1-i下标所有数的和，如果我们要求[l,r]区间的和就直接用a[r]-a[l - 1]就能算出，为什么a[l - 1]，因为如果直接减去a[l]就不能计算到原数组(转化为前缀和数组之前)中a[l]的值。

2.代码模板

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n + 1];
        for(int i = 1; i <= n; i++)     //用原数组计算前缀和
            a[i] = in.nextInt() + a[i - 1];
        while(m --> 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(a[r] - a[l - 1]);    //计算区间和
        }
    }
}

3.复杂度分析

• 时间复杂度:O(n)
• 空间复杂度:O(n)