1、前綴數(shù)組求和
1.1刷喜、案例
假設有一個數(shù)組arr残制，用戶總是非常頻繁的查詢arr中某一段的累加和，那么你應該如何組織數(shù)據(jù)掖疮，能讓這種查詢變得便利和快捷初茶？
1.2、方案1
使用二維數(shù)組的方式浊闪，分別將00的和放在二維數(shù)組的[0][0]位置恼布，將01的和放在二維數(shù)組的[0][1]...按此規(guī)則組合成一個二維數(shù)組
| L\R | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | arr[0] | arr[0]~arr[1]的和 | arr[0]~arr[2]的和 | arr[0]~arr[3]的和 |
| 1 | 無值 | arr[1] | arr[1]~arr[2]的和 | arr[1]~arr[3]的和 |
| 2 | 無值 | 無值 | arr[2] | arr[2]~arr[3]的和 |
| 3 | 無值 | 無值 | 無值 | arr[3] |
1.3螺戳、方案2
使用前綴數(shù)組（前綴和）來存儲（一維數(shù)組），前綴數(shù)組的第0個位置放00的和折汞，第1個位置放01的和...第n-1個位置放0n-1的和倔幼。當需要求arr數(shù)組LR之間的和時，算法為L==0?h[R]:h[R]-h[L-1]字支。
1.4凤藏、代碼實現(xiàn)
package com.yubin.algorithms;
/**
* 使用前綴數(shù)組求和
* 案例：假設有一個數(shù)組arr，用戶總是非常頻繁的查詢arr中某一段的累加和你如何組織數(shù)據(jù)堕伪，能讓這種查詢變得便利和快捷揖庄？
*
* 方案1:
* 使用二維數(shù)組的方式,分別將0~0的和放在二維數(shù)組的[0][0]位置, 0~1的和放在二維數(shù)組的[0][1]...按此規(guī)則組合二維數(shù)組
* 方案2:
* 使用前綴數(shù)組(前綴和)來存在(一維數(shù)組),前綴數(shù)組的第0個位置放0~0的和, 第1個位置放0~1的和 .. 第n-1個位置放0~n-1的和,
* 當需要求arr數(shù)組L~R之間的和時,算法為 L==0? h[R] : h[R] - h[L-1]
*
* 假設arr數(shù)組的長度為N
* 定義的二維數(shù)組是 h[N][N]
* 定義的一維數(shù)組是 h[N]
* @author YUBIN
* @create 2021-03-13
*/
public class Code0006_PreSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
RangeSum1 rangeSum1 = new RangeSum1(arr);
RangeSum2 rangeSum2 = new RangeSum2(arr);
System.out.println(rangeSum1.rangeSum(3, 5));
System.out.println(rangeSum2.rangeSum(3, 5));
}
// 原始遍歷L~R之間的元素求和的方式
private static class RangeSum1 {
private int[] arr;
public RangeSum1(int[] array) {
arr = array;
}
public int rangeSum(int L, int R) {
int sum = 0;
for (int i = L; i <= R; i++) {
sum += arr[i];
}
return sum;
}
}
// 使用前綴數(shù)組
private static class RangeSum2 {
private int[] preSum;
public RangeSum2(int[] array) {
int N = array.length;
preSum = new int[N];
preSum[0] = array[0];
for (int i = 1; i < N; i++) {
preSum[i] = preSum[i - 1] + array[i];
}
}
public int rangeSum(int L, int R) {
return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
}
}
}
1.5、兩種方案比較
第一種占用空間多欠雌，但是查詢的時候速度較第二種要快蹄梢。
如果查詢巨頻繁的話，第一種方案好富俄。
