题目描述
前缀和
思路
前缀和 初始化:
s[i] = s[i-1] + a[i]
计算 l - r 之间的和
s[r] - s[l-1]
时间复杂度
计算前缀和为o(1);
初始化前缀和为o(n);
JAVA 代码
import java.util.*;
import java.io.*;
class Main{
public static void main(String args[])throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int [] s1 = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
int n = s1[0];
int m = s1[1];
int [] s = new int[n+1];
int [] a = new int[n+1];
String [] s2 = in.readLine().split(" ");
//前缀和 从1开始算, 就不用加特判.
//但是也没办法直接用java stream流初始化 原数组.
for(int i = 1; i<= n; i++){
a[i] = Integer.parseInt(s2[i-1]);
//初始化 前缀和 数组
//每一个数为 [前一个数]+ [原数组中的数].
s[i] = s[i-1] + a[i];
}
for(int i = 0; i< m ; i++){
String[] s3 = in.readLine().split(" ");
int l = Integer.parseInt(s3[0]);
int r = Integer.parseInt(s3[1]);
//计算 l - r 区间
//s[l] = (a[1],a[l])的前缀和
//s[r] = (a[1],a[r])的前缀和
//s[r] - s[l-1] = 从r到l区间的和
System.out.println(s[r] - s[l-1]);
}
}
}