image.png
    数据结构都是由 连续+跳转组成

    数据结构累加和
    image.png
    这种方法占用户空间比较大 n*n

    前缀和数组
    image.png
    help数组每个位置的值 是原数组位置值 与之前位置值的累加和

    例如 求数组3-7范围的累加和 查出俩个数的值 相减
    image.png
    边界范围控制好
    image.png

    1. public static class RangeSum2 {
    3.         private int[] preSum;
    5.         public RangeSum2(int[] array) {
    6.             int N = array.length;
    7.             preSum = new int[N];
    8.             preSum[0] = array[0];
    9.             for (int i = 1; i < N; i++) {
    10.                 preSum[i] = preSum[i - 1] + array[i];
    11.             }
    12.         }
    14.         public int rangeSum(int L, int R) {
    15.             return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
    16.         }
    18.     }

    如果查询达到巨大无比 十几亿次 第一种好 不用减 可以直接拿到值