引入

数组区间求和问题，也称为前缀和问题，是一个常见的算法问题。解决这个问题一般有两种思路，分别是利用二维数组建表和利用一维前缀和数组。在不同的需求下这两种思路各有优点，所以本文对这两种思路总结一下。

思路一：二维数组建表

利用二维数组建表的思路就是将给定数组的每个区间和都存储起来，要查询哪个区间直接从表中取出来对应元素即可。例如给定一个数组[2,3,1,4,5]，建表的过程如下图所示：

思路二：一维前缀和数组

利用一维前缀和数组的思路没有利用二维数组建表直接，但是胜在预处理简便。例如给定一个数组[2,3,1,4,5]，只需要建立一个等长的前缀和数组，第i个元素存储从第0个元素到第i个元素的累加和。要查询[L,R]的区间和时，如果L为0，直接返回前缀和数组第R个元素；如果L不等于0，只需要用前缀和数组第R个元素减去第L-1个元素即可。

代码实现

二维数组建表：

package com.test;

public class rangeSum {
    private int[][] arr;

    public rangeSum(int[] arr) {
        this.arr = new int[arr.length][arr.length];
        setArr(arr);
    }

    public void setArr(int[] arr) {
        for(int i = 0; i < arr.length; i++){
            for(int j = i; j < arr.length; j++){
                if(i == j){
                    this.arr[i][j] = arr[j];
                }
                else{
                    this.arr[i][j] = this.arr[i][j-1] + arr[j];
                }
            }
        }
    }

    public int query(int L, int R){
        return arr[L][R];
    }
}

一维前缀和数组：

package com.test;

public class rangeSum {
    private int[] preSum;

    public rangeSum(int[] arr){
        preSum = new int[arr.length];
        setPreSum(arr);
    }

    public void setPreSum(int[] arr) {
        for(int i = 0; i < arr.length; i++){
            if(i == 0){
                preSum[i] = arr[i];
            }
            else{
                preSum[i] = preSum[i-1] + arr[i];
            }
        }
    }

    public int query(int L, int R){
        if(L == 0){
            return preSum[R];
        }
        return preSum[R] - preSum[L-1];
    }
}

两种方法的测试类为：

package com.test;

public class Test {
    public static void main(String[] args) {
        int[] arr = {2,3,1,4,5};
        rangeSum r = new rangeSum(arr);
        System.out.println(r.query(2,4));
    }
}

看完上面的思路，可能会有人觉得思路二看起来比思路一简便啊，那为什么还要写第一种呢？

事实上，抛开剂量谈毒性都是耍流氓。二维数组建表的思路优点是建表后，查询任意区间的时间复杂度为$O(1)$，非常高效，可以方便地处理多次查询的情况，避免重复计算。缺点是建表的时间复杂度为$O(n^2)$，空间复杂度也为$O(n^2)$，因此对于数据规模较大的情况，建表的时间和空间开销可能较大，而且当原数组发生修改时，需要重新建表，时间复杂度为$O(n^2)$，因此不适用于原数组频繁修改的情况；一维前缀和数组的思路优点是预处理前缀和数组的时间复杂度为$O(n)$，当原数组发生修改时，只需要重新计算前缀和数组，时间复杂度为$O(n)$，因此适用于原数组频繁修改的情况。

所以总的来说，二维数组建表适用于多次查询、原数组不频繁修改的情况，而一维前缀和数组适用于原数组频繁修改、数据规模较大的情况。