前缀和模板

一句话说明

前缀和是一种预处理技巧，通过空间换时间，将区间求和从O(n)优化到O(1)。

💻 模板代码

🎯 核心公式

一维前缀和

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

区间和 [left, right] = prefix[right+1] - prefix[left]

二维前缀和

prefix[i][j] = 从(0,0)到(i-1,j-1)的矩形和

矩形和 = prefix[row2+1][col2+1]
        - prefix[row1][col2+1]
        - prefix[row2+1][col1]
        + prefix[row1][col1]

差分数组

区间 [left, right] +val:
    diff[left] += val
    diff[right+1] -= val

适用场景

类型	适用场景	时间复杂度
一维前缀和	多次查询区间和	预处理O(n)，查询O(1)
二维前缀和	多次查询矩形和	预处理O(mn)，查询O(1)
差分数组	多次区间修改	预处理O(n)，修改O(1)
前缀和+哈希	子数组和问题	O(n)

💡 经典题目

题目	LeetCode	模板
区域和检索	303	一维前缀和
二维区域和检索	304	二维前缀和
和为K的子数组	560	前缀和+哈希
航班预订统计	1109	差分数组
拼车	1094	差分数组

Go 代码

// 一维前缀和
type PrefixSum struct {
    prefix []int
}
 
func NewPrefixSum(nums []int) *PrefixSum {
    n := len(nums)
    prefix := make([]int, n+1)
 
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + nums[i]
    }
 
    return &PrefixSum{prefix: prefix}
}
 
func (ps *PrefixSum) RangeSum(left, right int) int {
    return ps.prefix[right+1] - ps.prefix[left]
}
 
// 二维前缀和
type PrefixSum2D struct {
    prefix [][]int
}
 
func NewPrefixSum2D(matrix [][]int) *PrefixSum2D {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return &PrefixSum2D{}
    }
 
    m, n := len(matrix), len(matrix[0])
    prefix := make([][]int, m+1)
    for i := range prefix {
        prefix[i] = make([]int, n+1)
    }
 
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            prefix[i+1][j+1] = prefix[i][j+1] +
                               prefix[i+1][j] -
                               prefix[i][j] +
                               matrix[i][j]
        }
    }
 
    return &PrefixSum2D{prefix: prefix}
}
 
func (ps *PrefixSum2D) RegionSum(row1, col1, row2, col2 int) int {
    return ps.prefix[row2+1][col2+1] -
           ps.prefix[row1][col2+1] -
           ps.prefix[row2+1][col1] +
           ps.prefix[row1][col1]
}
 
// 差分数组
type Difference struct {
    diff []int
}
 
func NewDifference(nums []int) *Difference {
    n := len(nums)
    diff := make([]int, n)
 
    diff[0] = nums[0]
    for i := 1; i < n; i++ {
        diff[i] = nums[i] - nums[i-1]
    }
 
    return &Difference{diff: diff}
}
 
func (d *Difference) Increment(left, right, val int) {
    d.diff[left] += val
    if right+1 < len(d.diff) {
        d.diff[right+1] -= val
    }
}
 
func (d *Difference) Result() []int {
    n := len(d.diff)
    res := make([]int, n)
    res[0] = d.diff[0]
 
    for i := 1; i < n; i++ {
        res[i] = res[i-1] + d.diff[i]
    }
 
    return res
}

---

返回：算法模板