前缀和,顾名思义是一种求出数组前n项的和的方法,本质为对数组进行预处理然后对问题求解:
主要分为1维前缀和和多维前缀和:
1.1维前缀和求解方法:
1.前缀和公式s[i] = s[i - 1] + a[i]
2.进行直接查找
例题:
链接:活动 - AcWing
答案:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class TheTotalOfFront {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
//将读取的数进行转化
int n = scanner.nextInt(),m = scanner.nextInt();
//记录前n项的前缀和
int [] arr = new int[n + 1];
int temp;//记录临时数字
for(int i = 1; i <= n; i++){
temp = scanner.nextInt();
arr[i] = arr[i - 1] + temp;
}
while(m-- > 0){
//临时变量记录区间范围
int x = scanner.nextInt(),y = scanner.nextInt();
System.out.println(arr[y] - arr[x - 1]);
}
}
}
2.二维前缀和求解:
1.找出前缀和公式
2.直接运算
例题:
链接:活动 - AcWing
题解如下:
import java.util.Arrays;
import java.util.Scanner;
public class TheSumOfJuZhen {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(),m = scanner.nextInt(),q = scanner.nextInt();
//创建数组存储前n,m行的和
long [][] arr = new long[n + 1][m + 1];
//运算前n项和
for(int i = 1; i <= n ; i++){
for(int j = 1; j <= m ; j++){
//求前缀和
int temp = scanner.nextInt();
arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + temp;
}
}
// for (long[] a:arr) {
// System.out.println(Arrays.toString(a));
// }
//循环求值
while(q-- > 0){
//边界赋值
int a,b,c,d;
a = scanner.nextInt();
b = scanner.nextInt();
c = scanner.nextInt();
d = scanner.nextInt();
//输出前缀和
System.out.println(arr[c][d] - arr[c][b - 1] - arr[a - 1][d] + arr[a - 1][b - 1]);
}
}
}
前缀和知识点比较简单,算法思维也不难,就是推公式和注意细节
注:前面关于快速选择算法的代码错误,正确代码如下:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
public class QuickChoose {
static int n;
static int k;
public static void main(String[] args) throws IOException {
final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
final Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
int [] arr = new int[n];
//读入数据
// final String s1 = new Scanner(System.in).nextLine();
// String[] s = bufferedReader.readLine().split(" ");
for (int i = 0 ; i < n; i++){
arr[i] = scanner.nextInt();
}
// System.out.println(Arrays.toString(arr));
System.out.println(quickChoose(0,n - 1,arr,k));
bufferedReader.close();
}
//快速选择方法,该方法用于求出l到r区间范围内的第k个数
public static int quickChoose(int l,int r,int [] arr,int k){
//如果当前只有一个数存在
if(l == r){
return arr[l];
}
//否则进行排序和查找
int i = l - 1,j = r + 1,pivot = arr[l];
//修正本次必须返回j,j + 1
//当前元素区间不止为一个数时
while(i < j){
while(arr[++i] < pivot);
while(arr[--j] > pivot);
//如果满足区间元素不为1
if(i < j){
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//如果在左半部分,直接排序左边求解
int s1 = j - l + 1;
if(s1 >= k){
return quickChoose(l,i - 1,arr,k);
}else{
//否则排序右边数组
k = k - s1;
return quickChoose( i,r,arr,k);
}
}
}



