前缀和与差分数组

Posted on |

前缀和

计算一个长度为N的数组中元素和为K的连续子数组的个数?
如:在长度为3的数组[1,1,1]中元素和为2的连续子数组的个数为2,即[1,1], [1,1]

这里一个很简单的思路是枚举出原始数组所有的子数组，然后计算出子数组的元素和，判断是否等于K。问题是如何快速计算出子数组的元素和呢，这里可以使用前缀和的技巧。

1
2
3
4
       
origin = [1，3，2，4，5]      // 原始数组
       
prefix = [0，1，4，6，10，15] // 原始数组的前缀和数组

prefix[i]就是原始数组的前i项的和，我们可以使用下面的代码来构造前缀和数组

1
2
3
4
5
origin = int64[]{1,3,2,4,6}
prefix:= make(int64[], 0, len(origin)+1)
for idx:=range origin {
    prefix[idx+1] = prefix[idx]+origin[idx]
}

有了前缀和数组，我们就可以轻松的得出origin数组的(i,j)的元素和了,sum(i,j) = prefix[j+1]-prefix[i]

前缀和数组适用于多次求数组的连续子数组的元素和问题。

差分数组

差分数组和前缀和数组有异曲同工之妙。考虑下面这个问题：
给你一个长度为N的数组，和几组子数组元素的变化(同增同减)，求变化后的数组元素。如,长度为5的数组[2,3,5,1,8],进行三组变化，在索引(0,2)(包含两端点)的元素上加2， 在(1,4)的元素上减1，在(2,3)的元素上加3, 求变化后的数组？

1
2
3
4
原数组:[2,3,5,1,8]
(0,2)加2后:[4,5,7,1,8]
(1,4)减1后:[3,4,6,0,7]
(2,3)加3后:[3,4,9,3,7]

一个简单的想法是，遍历所有的变更，将每一个变更元素都在原数组上反映出来，但是这样会频繁的访问原数组，时间复杂度随着变更子数组的长度和的变化而变化。我们可以考虑差分数组来优化。

1
2
3
4
5
6
原数组:[2,3,5,1,8]

差分数组:[2,1,2,-4,7]

当i=0时，`diff[i] = origin[i]`;
当i>0时，`diff[i] = origin[i]-origin[i-1]`;

通过差分数组，我们可以还原出来原数组，原数组的第i项就是差分数组的前i项之和。

在原数组的(i,j)上加上x等效于将 diff[i]+=x, diff[j]-=x, 如此，我们可以将对原数组的更改转化成对差分数组的更改，无论变更的子数组的长度为多少，我们都只需要在差分数组上更新两次，有效的减少了时间复杂度。