Blog of AgioPan
0%

数据结构与算法自学笔记（22）- 一维差分与等差数列差分

Posted on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class047的内容，总结了一维差分与等差数列差分的核心思想和应用。差分技巧是处理区间修改问题的重要工具，特别适用于大量区间操作后的批量查询场景。

前置知识

在学习差分数组之前，需要掌握以下基础知识：

  • 数组的基本操作
  • 前缀和的概念与应用
  • 理解数组索引和边界处理

047【必备】一维差分与等差数列差分

核心概念

一维差分的基本思想

一维差分是一种优化区间修改操作的技巧：

  • 原理：通过维护一个差分数组，将区间修改转化为两个单点修改
  • 适用场景：多次区间修改，最后统一查询所有位置的值
  • 限制：不支持边操作边查询，需要先完成所有修改再构建最终数组

等差数列差分

等差数列差分是一维差分的扩展，用于处理区间内加等差数列的操作：

  • 核心特性：等差数列的二阶差分是常数
  • 应用场景：需要在区间内按等差数列规律增加数值
  • 实现方式：通过二阶差分数组进行操作，最后两次前缀和还原

题目一：航班预订统计

问题描述

这里有n个航班，它们分别从1到n进行编号。有一份航班预订表bookings，表中第i条预订记录bookings[i] = [firsti, lasti, seatsi]意味着在从firsti到lasti（包含firsti和lasti）的每个航班上预订了seatsi个座位。

请你返回一个长度为n的数组answer，里面的元素是每个航班预定的座位总数。

测试链接：https://leetcode.cn/problems/corporate-flight-bookings/

核心思想

使用差分数组优化区间修改操作：

  1. 差分数组构建：diff[i] 记录 ans[i] 相对于 ans[i-1] 的变化量
  2. 区间修改转化：对于预订 [first, last, seats]：
    • diff[first] += seats：从first开始增加seats
    • diff[last + 1] -= seats：从last+1开始撤销增加效应
  3. 结果还原：通过计算差分数组的前缀和得到最终结果ans[i] = ans[i-1] + diff[i]

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        """
        使用差分数组优化区间修改操作
        时间复杂度：O(m + n)，空间复杂度：O(n)
        """
        # 差分数组，长度 n+2 是为了方便处理边界，如 book[1]+1 可能达到 n+1
        diff = [0] * (n + 2)
        
        # 根据每个预订记录，更新差分数组
        for first, last, seats in bookings:
            diff[first] += seats
            if last + 1 <= n: # 边界检查
                diff[last + 1] -= seats
        
        # 计算前缀和来还原最终的座位数数组
        ans = [0] * n
        # ans[0] 就是 diff[1] 的值 (因为航班从1开始编号)
        ans[0] = diff[1]
        for i in range(1, n):
            # 当前航班的座位数 = 上一个航班的座位数 + 差分值
            ans[i] = ans[i-1] + diff[i+1] # diff的索引比ans大1
            
        return ans

算法分析

  • 时间复杂度：O(m + n)，其中m是预订次数，n是航班数量
  • 空间复杂度：O(n)
  • 核心优势：将每次O(n)的区间修改优化为O(1)的两次单点修改

题目二：等差数列差分模板

问题描述

一开始1n范围上的数字都是0，一共有m个操作，每次操作为(l,r,s,e,d)表示在lr范围上依次加上首项为s、末项为e、公差为d的数列。m个操作做完之后，统计1~n范围上所有数字的最大值和异或和。

测试链接：https://www.luogu.com.cn/problem/P4231

过两遍前缀和
反向推导

核心思想

使用二阶差分处理等差数列的区间加操作：

  1. 数学原理：等差数列的二阶差分是常数
  2. 操作分解：在二阶差分数组上进行四个关键点修改
  3. 结果构建：通过两次前缀和运算还原最终数组

关键函数解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def set_arithmetic_sequence(l, r, s, e, d):
    """
    在二阶差分数组上进行修改，以实现对原数组的等差数列范围加。
    这是通过数学推导得出的在二阶差分数组上的四个关键点修改。
    """
    arr[l] += s #在起始位置加上首项
    arr[l + 1] += d - s # 这确保了从位置l+1开始，一阶差分增加d（公差）
    arr[r + 1] -= (d + e) #在区间结束后，需要"撤销"等差数列的影响，因为后续的数字不会再增加
    arr[r + 2] += e #补偿操作，确保边界正确

def build():
    """
    通过两次前缀和运算，从二阶差分数组还原出最终数组。等差数列有一个重要性质：二阶差分是常数
    第一次前缀和：arr 从二阶差分数组变为一阶差分数组。
    第二次前缀和：arr 从一阶差分数组变为最终的结果数组。
    """
    # 第一次前缀和
    for i in range(1, n + 2):
        arr[i] += arr[i - 1]
    # 第二次前缀和
    for i in range(1, n + 1):
        arr[i] += arr[i - 1]

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
MAXN = 10000005
arr = [0] * MAXN
n, m = 0, 0

def main():
    """
    核心思想：二阶差分 (Difference of Differences)
    1. 对一个数组`a`进行范围`[l, r]`加一个常数`c`，可以在其一阶差分数组`b`上
       通过`b[l]+=c`, `b[r+1]-=c`实现。
    2. 对一个数组`a`进行范围`[l, r]`加一个等差数列，其变化在一阶差分数组`b`上表现为：
       `b[l]`增加首项`s`，`b[l+1...r]`范围增加公差`d`，`b[r+1]`有一个特殊变化。
    3. 这个“范围加常数”的操作，又可以被一个二阶差分数组`c`来优化。
    4. `set`函数中的四次修改，就是将“加等差数列”这一复杂操作，
       分解为在二阶差分数组`c`上的四个单点修改。
    5. 所有修改完成后，对`c`做一次前缀和得到`b`，再对`b`做一次前缀和得到最终的`a`。
    """
    global n, m
    lines = sys.stdin.readlines()
    line_iter = iter(lines)
    
    while True:
        try:
            n_m_line = next(line_iter)
            if not n_m_line: break
            n, m = map(int, n_m_line.strip().split())
            
            # 清零 arr 数组以处理多个测试用例
            # 只需要清到可能被修改的最大位置即可，这里为了简单直接清一部分
            max_r = 0
            
            # 读取m个操作并更新二阶差分数组
            ops = []
            for _ in range(m):
                l, r, s, e = map(int, next(line_iter).strip().split())
                ops.append((l, r, s, e))
                max_r = max(max_r, r)

            for i in range(max_r + 3): # 清理数组
                arr[i] = 0

            for l, r, s, e in ops:
                if r == l: # 公差为0的特殊情况
                    d = 0
                else:
                    d = (e - s) // (r - l)
                set_arithmetic_sequence(l, r, s, e, d)

            # 还原最终数组
            build()
            
            # 计算最大值和异或和
            max_val = 0
            xor_sum = 0
            for i in range(1, n + 1):
                max_val = max(max_val, arr[i])
                xor_sum ^= arr[i]
            
            print(f"{xor_sum} {max_val}")

        except StopIteration:
            break

算法分析

  • 时间复杂度：O(m + n)
  • 空间复杂度：O(n)
  • 核心技巧：二阶差分 + 两次前缀和

题目三：水位高度计算

问题描述

一群人落水后求每个位置的水位高度。每个人落水会产生复杂的水波模式，需要计算所有水波叠加后的最终水位。

测试链接：https://www.luogu.com.cn/problem/P5026

问题三描述可视化
问题三不越界

核心思想

将复杂的水波描述分解为四个等差数列的叠加，使用OFFSET技巧处理负坐标：

  1. 水波分解：每次落水产生四个等差数列段
  2. 坐标处理：使用OFFSET避免负数索引问题
  3. 叠加计算：多次调用等差数列差分函数

关键函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
OFFSET = 30001  # 数值保护，防止索引越界

def fall(v, x):
    """
    一个人落水，会产生四个等差数列的水波，调用四次set函数来模拟。
    """
    set_arithmetic_sequence(x - 3 * v + 1, x - 2 * v, 1, v, 1)
    set_arithmetic_sequence(x - 2 * v + 1, x, v - 1, -v, -1)
    set_arithmetic_sequence(x + 1, x + 2 * v, -v + 1, v, 1)
    set_arithmetic_sequence(x + 2 * v + 1, x + 3 * v - 1, v - 1, 1, -1)

def set_arithmetic_sequence(l, r, s, e, d):
    """
    与上题完全相同的二阶差分修改函数，但所有索引都加上了 OFFSET。
    OFFSET 技巧：
    通过给所有位置索引加上一个大的偏移量，可以确保即使 `l` 是负数，
    `l + OFFSET` 也是一个合法的正数数组下标，从而避免了复杂的边界条件判断。
    """
    arr[l + OFFSET] += s
    arr[l + 1 + OFFSET] += d - s
    arr[r + 1 + OFFSET] -= d + e
    arr[r + 2 + OFFSET] += e

def build():
    """
    同样通过两次前缀和运算，从二阶差分数组还原出最终的水位高度数组。
    """
    # 数组足够大，只需要计算到受影响的最右边界即可
    # 简化处理，直接使用 m + OFFSET
    for i in range(1, m + OFFSET * 2):
        arr[i] += arr[i - 1]
    for i in range(1, m + OFFSET * 2):
        arr[i] += arr[i - 1]

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
# 湖泊最大宽度
MAXN = 1000001
# 数值保护，防止索引越界
OFFSET = 30001
# 准备一个足够大的数组来容纳所有可能的位置
arr = [0] * (OFFSET + MAXN + OFFSET)
n, m = 0, 0

def main():
    """
    核心思想：
    1. 将题目中复杂的水波描述，分解为四个等差数列的叠加。
    2. 使用与上一题完全相同的“二阶差分”技巧来处理多个等差数列的范围增加操作。
    3. 使用 OFFSET 技巧来优雅地处理可能为负数的位置索引，避免边界判断。
    4. 所有落水操作完成后，通过两次前缀和还原出每个位置的最终水位。
    """
    global n, m
    lines = sys.stdin.readlines()
    line_iter = iter(lines)
    
    while True:
        try:
            n_m_line = next(line_iter)
            if not n_m_line: break
            n, m = map(int, n_m_line.strip().split())

            # 找到可能影响的最大范围，用于清理数组
            max_coord = 0
            ops = []
            for _ in range(n):
                v, x = map(int, next(line_iter).strip().split())
                ops.append((v, x))
                max_coord = max(max_coord, x + 3 * v)

            for i in range(max_coord + OFFSET + 2):
                arr[i] = 0

            # 对每次落水，更新二阶差分数组
            for v, x in ops:
                fall(v, x)
            
            # 还原最终水位
            build()
            
            # 收集并打印 1~m 位置的答案
            # 正式位置 1...m 对应于 arr 数组中的 OFFSET+1...OFFSET+m
            start = OFFSET + 1
            result = [str(arr[i]) for i in range(start, start + m)]
            print(" ".join(result))

        except StopIteration:
            break

算法分析

  • 时间复杂度：O(n + m)
  • 空间复杂度：O(n + OFFSET)
  • 核心技巧：OFFSET处理负坐标 + 复杂水波分解

差分技巧总结

1. 一维差分的应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 适用情况：
# 1. 大量区间修改操作
# 2. 最后统一查询所有位置
# 3. 不需要边操作边查询

# 基本操作：
def range_add(diff, l, r, val):
    """区间[l,r]增加val"""
    diff[l] += val
    diff[r + 1] -= val

def build_result(diff, n):
    """构建最终结果"""
    result = [0] * n
    result[0] = diff[0]
    for i in range(1, n):
        result[i] = result[i-1] + diff[i]
    return result

2. 等差数列差分的核心原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 数学基础：
# 原数组：a[0], a[1], a[2], ...
# 一阶差分：b[i] = a[i] - a[i-1]
# 二阶差分：c[i] = b[i] - b[i-1]

# 等差数列性质：
# 等差数列的一阶差分是常数
# 等差数列的二阶差分是0（除了边界）

# 操作模板：
def arithmetic_sequence_add(arr, l, r, s, e, d):
    """在l~r范围加等差数列[s,s+d,s+2d,...,e]"""
    arr[l] += s
    arr[l + 1] += d - s
    arr[r + 1] -= (d + e)
    arr[r + 2] += e

3. 边界处理技巧

1
2
3
4
5
6
7
8
9
10
# OFFSET技巧：处理负坐标
OFFSET = 30001
real_index = coordinate + OFFSET

# 边界扩展：防止越界
arr = [0] * (n + 2)  # 额外空间处理边界

# 范围检查
if r + 1 <= n:
    diff[r + 1] -= val

复杂度分析对比

方法 区间修改 单点查询 区间查询 适用场景
暴力 O(n) O(1) O(n) 修改少，查询多
差分数组 O(1) O(n) O(n) 修改多，批量查询
线段树 O(log n) O(log n) O(log n) 边修改边查询

学习建议

1. 理解差分本质

  • 差分是前缀和的逆运算
  • 区间修改转化为端点修改
  • 适用于修改多查询少的场景

2. 掌握模板套路

  • 熟练掌握一维差分的基本模板
  • 理解等差数列差分的数学原理
  • 练习边界处理和特殊情况

3. 注意实现细节

  • 数组大小的合理设计
  • 索引边界的仔细处理
  • OFFSET技巧的灵活运用

4. 扩展应用

  • 二维差分矩阵
  • 树上差分
  • 线段树lazy标记的差分思想

5. 调试技巧

  • 验证差分数组的正确性
  • 检查前缀和构建过程
  • 测试边界情况和特殊输入

通过掌握差分数组的核心思想和实现技巧，可以高效解决各种区间修改问题。关键在于理解差分与前缀和的关系，以及合理的边界处理策略。