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)

参考

前缀和技巧

【朝夕的ACM笔记】算法基础-前缀和