Links

01.前缀和

一、什么是前缀和?

1.1 一维前缀和

  • 一个一维数组X,和它的前缀和数组Y。
  • 那么满足:
    • Y[0] = X[0]
    • Y[1] = X[0] + X[1]
    • Y[2] = X[0] + X[1] + X[2]
    • ...
    • Y[n] = X[0] + X[1] + ... + X[n]

1.2 二维前缀和

  • 一个二维数组A,和他的前缀和数组B
  • 那么满足:
    • B[0,0] = A[0,0]
    • B[0,1] = A[0,0] + A[0,1]
    • B[1,0] = A[0,0] + A[1,0]
    • B[1,1] = A[0,0] + A[0,1] + A[1,0] + A[1,1]
    • ...
    • 简单描述就是一片矩形区域内的和

二、计算前缀和

2.1 一维前缀和

let nums: [Int] = [...]
// 前缀和数组
var pSum: [Int] = Array(repeating: 0, count: nums.count)
for i in 0..<nums.count {
if i == 0 {
pSum[0] = nums[0]
}
else {
pSum[i] = pSum[i - 1] + nums[i]
}
}

2.2 二维前缀和

  • 二维前缀和其实就是一个矩阵内值的和,而矩阵又可以由两个列数或行数少一的子矩阵组合后,去除重复的部分,然后再加上右下角的值来构成。
    • B[x,y] = B[x-1,y] + B[x,y-1] - B[x-1, y-1] + A[x,y]
let nums: [[Int]] = [...]
var pSum: [[Int]] = Array(repeating: Array(repeating: 0, count: nums.first?.count ?? 0),
count: nums.count)
for y in 0..<nums.count {
for x in 0..<nums[y].count {
if x == 0 && y == 0 {
pSum[0][0] = nums[0][0]
}
else if x == 0 {
pSum[0][y] = pSum[0][y-1] + nums[x][y]
}
else if y == 0 {
pSum[x][0] = pSum[x-1][0] + nums[x][y]
}
else {
pSum[x][y] = pSum[x-1][y] + pSum[x][y-1] - pSum[x-1][y-1] + nums[x][y]
}
}
}

三、前缀和的应用

  • 前缀和是一种预处理,用来降低数据查询的时间复杂度。
  • 例如:
    • 一个n长度的数组,进行m次查询,每次随机长度,输出每次的和
  • 上面的例子如果暴力解的话,每次都要重头开始到指定下标进行遍历
  • 如果使用前缀和,进行了预处理之后,可以直接查出结果
    • 假设l r 为给定的区间,计算区间内的和
    • result = x[r] - x[l-1]
    • 时间复杂度为O(n+m)

参考