数组-差分数组

• 理解比较简单，需要掌握。
• 应用：快速处理区间加减操作（对数列中区间[L,R]上的数加上x）。
• 参考: https://gwx123456.blog.luogu.org/ci-fen

0、定义

• 对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：
• 显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。
• 上面为专业术语，通俗点说就是前面的元素减后面的元素得到差分数组。
• 复杂度
  • 时间复杂度：O(1)
  • 空间复杂度：O(n)

1、操作

• 1、定义差分数组：d = make([]int, len(arr)+1) // 多一位
• 2、求差分数组：d[0]=arr[i] 或者d[i]=arr[i]-arr[i-1] (i>=1)
• 3、遍历操作：start, end, count => d[start]=d[start]+count, d[end+1]=d[end+1]-count
• 4、求结果：res[i] := 求和/累加和/前缀和(d[0]+...+d[i])

示例

首先一个数组 
1 2 3 4 5 6 7 
那么差分之后 
1 1 1 1 1 1 1

2、Go实现

package main

import "fmt"

func main() {
    origin := []int{1, 4, 8, 10, 5, 2, 16} // 开始的数组
    d := make([]int, len(origin)+1)        // 多1位，在做d[end+1]不会超出范围
    // 1.计算差分数组
    d[0] = origin[0] // 第一项
    for i := 1; i < len(origin); i++ {
        d[i] = origin[i] - origin[i-1]
    }
    fmt.Println(origin) // [1 4 8 10 5 2 16]
    fmt.Println(d)      // [1 3 4 2 -5 -3 14 0]
    // 验证 origin[i] = 求和(d[0]+..+d[i]
    arr := make([]int, 0)
    total := 0
    for i := 0; i < len(d)-1; i++ {
        total = total + d[i]
        arr = append(arr, total)
    }
    fmt.Println(arr) // [1 4 8 10 5 2 16]

    // 2.操作
    // 开始坐标，结束坐标，操作次数
    operation := [][]int{
        {1, 2, 1},
        {2, 5, 1},
        {0, 6, 1},
    }
    for i := 0; i < len(operation); i++ {
        start := operation[i][0]
        end := operation[i][1]
        count := operation[i][2]
        // 差分操作
        d[start] = d[start] + count
        d[end+1] = d[end+1] - count
        // 正常模拟操作
        for j := start; j <= end; j++ {
            arr[j] = arr[j] + count
        }
    }
    fmt.Println(arr) // 正常模拟操作的结果: [2 6 11 12 7 4 17]
    res := make([]int, 0)
    total = 0
    for i := 0; i < len(d)-1; i++ {
        total = total + d[i]
        res = append(res, total)
    }
    fmt.Println(res) // 差分计算的结果：[2 6 11 12 7 4 17]
}

3、Leetcode