java前缀和（原理+代码）

---

Prefix sum（ 前缀和 ）

用于解决原数组不变，多次求区间和的问题。

输入整数数组 [ n u m s ] [ nums ] [nums] 和查询数组 [ f i n d S u m ] [ findSum ] [findSum]，每个查询包含两个整数 l l l 和 r r r ，表示查询第 l l l 个数到第 r r r 个数的和
（注意 : 是第 l l l 个数到第 r r r 个数，也就是 n u m s [ 0 ] nums [ 0 ] nums[0] 为第一个数）

• 对于 n n n 个数，先创建一个长度为 n + 1 n+1 n+1 的前缀和数组 [ p r e f i x S u m ] [prefixSum] [prefixSum]
• p r e f i x S u m [ 0 ] = 0 prefixSum[0]=0 prefixSum[0]=0
• p r e f i x S u m [ i ] = p r e f i x S u m [ i − 1 ] + n u m s [ i − 1 ] prefixSum[i]=prefixSum[i-1]+nums[i-1] prefixSum[i]=prefixSum[i−1]+nums[i−1]
• s u m ( l , r ) = p r e f i x S u m [ r ] − p r e f i x S u m [ l − 1 ] sum(l,r)=prefixSum[r]-prefixSum[l-1] sum(l,r)=prefixSum[r]−prefixSum[l−1]

证明

p r e f i x S u m 简 写 为 p r e prefixSum简写为pre prefixSum简写为pre
p r e [ l − 1 ] = p r e [ 0 ] + p r e [ 1 ] + … + p r e [ l − 2 ] + p r e [ l − 1 ] pre[l-1]=pre[0]+pre[1]+ \ldots+pre[l-2]+pre[l-1] pre[l−1]=pre[0]+pre[1]+…+pre[l−2]+pre[l−1]
p r e [ r ] = p r e [ 0 ] + p r e [ 1 ] + … + p r e [ l − 1 ] + p r e [ l ] + p r e [ l + 1 ] … + p r e [ r − 1 ] + p r e [ r ] pre[r]=pre[0]+pre[1]+ \ldots+pre[l-1]+pre[l]+pre[l+1] \ldots+pre[r-1]+pre[r] pre[r]=pre[0]+pre[1]+…+pre[l−1]+pre[l]+pre[l+1]…+pre[r−1]+pre[r]
p r e [ r ] − p r e [ l − 1 ] = p r e [ l ] + p r e [ l + 1 ] + … + p r e [ r − 1 ] + p r e [ r ] pre[r]-pre[l-1]=pre[l]+pre[l+1]+ \ldots+pre[r-1]+pre[r] pre[r]−pre[l−1]=pre[l]+pre[l+1]+…+pre[r−1]+pre[r]

输入 :
[ n u m s ] [ nums ] [nums] = [ 1，2，3，4，5，6，7，8，9，10，11 ]
[ f i n d S u m ] [ findSum ] [findSum] = [ [ 1，5 ]，[ 6，11 ]，[ 1，11 ] ]

输出 :
[ 15，51，66 ]

i n d e x index index	0	1	2	3	4	5	6	7	8	9	10	11
[ n u m s ] [ nums ] [nums]	1	2	3	4	5	6	7	8	9	10	11	/
[ p r e f i x S u m ] [ prefixSum ] [prefixSum]	0	1	3	6	10	15	21	28	36	45	55	66

public void getSum(int[] nums, int[][] findSum)
{
    int[] prefixSum = new int[nums.length + 1];

    for (int i = 1; i < prefixSum.length; i++)
    {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
    }

    for (int[] find : findSum)
    {
        int l = find[0];
        int r = find[1];

        System.out.print(prefixSum[r] - prefixSum[l - 1]+" ");

		//如果 findSum 中的 l 和 r 为原数组下标而不是第 l / r 个数，可以 :
		//int l = find[0] + 1; 例 : 原数组下标 0 对应第 1 个数
		//int r = find[1] + 1;
		//或者 :
		//prefixSum[r +1] - prefixSum[l]
    }
}

补充

让 [ p r e f i x S u m ] [prefixSum] [prefixSum] 长的度比 [ n u m s ] [nums] [nums] 多 1 是为了设置 p r e f i x S u m [ 0 ] = 0 prefixSum[0]=0 prefixSum[0]=0，然后让 p r e f i x S u m [ 1 ] prefixSum[1] prefixSum[1] 保存 [ n u m s ] [nums] [nums] 的第一个数的前缀和。

因为如果 p r e f i x S u m [ 0 ] prefixSum[0] prefixSum[0] 保存的是 [ n u m s ] [nums] [nums] 第一个数的前缀和，在计算 s u m ( l , r ) sum(l,r) sum(l,r) 的时候需要减去第 l l l 个数的上一个数的前缀和，当 l = 1 l=1 l=1 时，因为 [ p r e f i x S u m ] [prefixSum] [prefixSum] 的第一个数就是 [ n u m s ] [nums] [nums] 第一个数的前缀和，所以在寻找 [ n u m s ] [nums] [nums] 第一个数上一个数的前缀和时就会导致数组越界。

另一种解决方法是在计算 p r e f i x S u m [ r ] − p r e f i x S u m [ l − 1 ] prefixSum[r] - prefixSum[l - 1] prefixSum[r]−prefixSum[l−1] 前进行判断，如果 l = 1 l=1 l=1 则直接返回 p r e f i x S u m [ r ] prefixSum[r] prefixSum[r]，由于每次查询都要多进行一次判断，所以不建议采用这种写法。

---