题目描述

给定一个数组,求指定范围的和！

样例

输入样例

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例

3
6
10

算法1

(前缀和) $O(1)$

思想: 就是初始化一个前缀和数组,公式的话为s[i] = s[i - 1] + a[i];比如给定一个数组a==>2 1 3 6 4,那么他的前缀和数组就是s==>2 3 6 12 4,(s[1] = s[0] + a[1] = 2;s[2] = s[2 - 1] + a[2] = 3…)注意i的下标从1开始,要不公式不通用了.假如说现在要求1 - 2 之间的和,那么只需要让s[2] - s[1 - 1]的结果就是答案.

优点: 如果用暴力算法的话,就是每次输入一行左右边界,就得遍历一下数组,那么当输入的越多,则时间复杂度越高,即$O(n)$,如果用前缀和方法的话,首先初始化一个前缀和数组,然后每次只需要算一下s[r] - s[l - 1]即可,那么时间复杂度就变成了$O(1)$

时间复杂度: $O(1)$

参考文献: y总

Java 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static final int N = 100010;
    public static int[] a = new int[N];
    public static int[] s = new int[N];
    public static int n,m;
    public static void main(String[] args) throws IOException{
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        String[] str_1 = scan.readLine().split(" ");
        n = Integer.parseInt(str_1[0]);
        m = Integer.parseInt(str_1[1]);

        String[] str_2 = scan.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str_2[i - 1]);

        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

        int[] res = new int[m + 1];
        for (int i = 1; i <= m; i++){
            String[] str_3 = scan.readLine().split(" ");
            int l = Integer.parseInt(str_3[0]);
            int r = Integer.parseInt(str_3[1]);
            res[i] = s[r] - s[l -1];
        }

        for (int i = 1; i <= m; i++) System.out.println(res[i]);
    }
}