【算法02】前缀和

问题 ：给定一个长度为 N 的整数数组以及两个数字 L 和 R，我们的目标是计算该数组中 L 到 R 索引之间的数字的总和。

解决方案一：

我们可以创建一个 N x N 的二维数组进行预计算，这个数组将保存从 0 到 N 之间所有区间的和。

public  class RangeSum1 {
    private int[] arr;
    private int[][] db;
    public RangeSum1(int[] arr) {
        this.arr = arr;
        db = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            db[i][i] = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                db[i][j] = db[i][j - 1] + arr[j];
            }
        }
    }
    public int rangeSum(int L, int R) {
        return db[L][R];
    }
}

优点：

1. 适合于查询次数非常多的情况。在进行大量查询时，该方法比解决方案二少了一次减法运算。

缺点：

1. 预计算阶段需要创建二维数组，其计算量达到 N x N / 2的级别。

解决方案二：

我们也可以创建一个长度为 n 的一维数组（记为 H），其中每一格保存从索引 0 到当前索引的前缀和。在查询时，如果 L 是 0，则直接返回 H[R] ；如果 L 不是 0，则返回 H[R] - H[L-1] 的结果。

public  class RangeSum2 {
    private int[] preSum;

    public RangeSum2(int[] arr) {
        int N = arr.length;
        preSum = new int[N];
        preSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            preSum[i] = preSum[i - 1] + arr[i];
        }
    }

    public int rangeSum(int[] arr, int L, int R) {
        return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
    }

}

优点：

1. 更适合于查询次数不多的情况。
2. 构建数组只需要遍历一次原始数组，因此减少了查询次数，减小了运算量。

缺点：

1. 当数据量过大时，其查询效率不如方法一高。