Java 前缀和算法题目练习

前缀和

题目解析：在一个数组中查询对应区间的和，会查询多次。

算法思想：

• 暴力解法：每次查询都进行一次遍历，时间复杂度 O(n*m)。
• 前缀和解法：新定义一个数组，每一个下标存放的值是要查询数组的前下标对应值的和。这样我们在访问某一个区间的时候，直接利用这个数组就非常快速。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n + 1];
        // 此时我们让其下标从 1 开始，这样可以省略边界问题考虑
        arr[0] = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        // 题目意思就是给了我们长度是 n 的数组，但是会有 m 查询
        // 1.首先定义一个新的数组，其每一个下标对应的值是其从 arr[1] 开始到这个下标值的和
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - ] + arr[i];
        }
         (m > ) {
               in.nextInt();
               in.nextInt();
            System.out.println(dp[r] - dp[l - ]);
            m--;
        }
    }
}