定义

前缀和算法：一种用于高效计算数组前缀和的算法。前缀和是指数组中某个位置之前（包括该位置）所有元素的和。基本思想是通过一次遍历数组，计算每个位置的前缀和，并将其存储在一个新的数组中。然后，可以通过查询新数组中的元素，快速计算出任意子数组的和。

例如有个数组arr的长度为6，这个时候就可以通过遍历一次数组，计算每个位置的前缀和得到数组pre，此时
pre数组0位置的值为：arr数组0-0位置的值
pre数组1位置的值为：arr数组0-1位置的值
pre数组2位置的值为：arr数组0-2位置的值
……
以此类推
这个时候如果有个需求，需要计算arr数组中L位置到R位置的值的和，这个时候可以通过一下方式得到：
如果L=0，则这个值为pre[R]的值
如果L≠0，则这个值为pre[R]-pre[L-1]的值

代码示例

public class PreSum {

    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 11, 10, 9, 45, 1, 6, 7, 9, 12};
        int[] pre = getPre(arr);
        int sum = arrSum(pre, 1, 5);
        System.out.print("原始数组为：");
        printArr(arr);
        System.out.print("前缀和数组为：");
        printArr(pre);
        System.out.println("原始数组1-5位置的和为：" + sum);
    }

    public static int arrSum(int[] pre, int l, int r) {
        if (l == 0) {
            return pre[r];
        } else {
            return pre[r] - pre[l - 1];
        }
    }

    public static void printArr(int[] arr) {
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    /**
     * 获取前缀和数组
     * @param arr   数组
     * @return      前缀和数组
     */
    public static int[] getPre(int[] arr) {
        int[] pre = new int[arr.length];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            pre[i] = sum;
        }
        return pre;
    }

}

打印结果为：

原始数组为：5 1 6 11 10 9 45 1 6 7 9 12 
前缀和数组为：5 6 12 23 33 42 87 88 94 101 110 122 
原始数组1-5位置的和为：37