开发者日记

外观

一文搞懂差分数组：从 O(nm) 到 O(n+m) 的区间叠加统计 ​

问题背景：为什么区间叠加容易写成暴力 ​

会议室预订、航班座位占用、优惠券叠加、流量打点统计，都可以抽象成同一种模型：给定若干个区间 [start, end]，每个区间会让某一指标增加固定值；最后需要知道每个时间点或位置上的总占用量。

最直观的做法是遍历每个区间，再遍历区间内部所有点：

python
def range_add_bruteforce(events, n):
    count = [0] * n
    for start, end, value in events:
        # 每来一个区间，就把内部所有位置逐个加一次
        for i in range(start, end + 1):
            count[i] += value
    return count

如果有 m 个区间，单个区间平均长度为 L，时间复杂度是 O(mL)，最坏可达到 O(nm)。在会议室场景中，一天可能只有 96 个 15 分钟粒度，性能尚可；但航班座位统计可能覆盖一整年、多个舱位和多批预订，暴力更新很快变成性能瓶颈。

差分数组（difference array）正是为这种“多次区间增加、最后统一查询”的场景设计的。它把对整段区间的修改压缩成两个端点操作，再通过一次前缀和还原结果。

方案对比：暴力、普通前缀和与差分数组 ​

普通前缀和适合“静态数组多次查询区间和”，但它不能直接处理区间更新。差分数组可以看作前缀和的逆向使用：先记录变化量，再沿数组方向累积。

方案区间增加最终还原适用场景主要问题
暴力更新O(L)O(n)区间少、长度短区间长或数量多时退化明显
线段树O(log n)O(n 或查询)动态更新、动态查询混合实现复杂，常数较大
差分数组O(1)O(n)批量区间增加后统一统计不适合每次更新后立刻查询
前缀和不擅长更新O(1) 查询静态区间求和不能高效表达区间加法

下面这张图展示了差分数组的核心流程：每个预订只影响两个端点，最后从左到右做一次前缀累积。

读取预订区间start / end / value标记差分端点diff[start] += value结束位置抵消diff[end+1] -= value前缀和还原current += diff[i]得到占用量峰值 / 冲突 / 超载

核心原理：用两个端点表示整段变化 ​

假设数组 count[i] 表示第 i 个位置的实际占用量，定义差分数组：

text
diff[0] = count[0]
diff[i] = count[i] - count[i - 1]

如果希望让闭区间 [left, right] 内所有元素都增加 value，实际只需要：

python
diff[left] += value
if right + 1 < n:
    diff[right + 1] -= value

原因是前缀还原时，diff[left] 的增加会从 left 开始一直影响后续位置；而在 right + 1 处减去同样的值后，影响正好在区间外结束。

如果不判断边界，也可以把数组开成 n + 1。多出来的位置不会参与最终结果，却能安全承接抵消标记，代码更简洁。

实战一：会议室预订的最大并发数 ​

题目模型 ​

给定若干会议 [start, end]，时间按小时或离散时间片编号，会议占用闭区间 [start, end]。求同一时间段最多有多少场会议同时进行。

例如：

python
bookings = [
    [1, 3],
    [2, 4],
    [4, 5],
]

时间点 2、3 都有两场会议，时间点 4 也有两场会议，因此最大并发数为 2。

Python 可运行代码 ​

python
def max_meeting_rooms(bookings, n):
    """
    bookings: 每个元素为 [start, end]，表示闭区间预订
    n: 时间点编号范围为 0 到 n - 1
    返回：最大同时进行会议数
    """
    # 多开一个位置，用于承接 end + 1 的抵消标记
    diff = [0] * (n + 1)

    for start, end in bookings:
        diff[start] += 1
        diff[end + 1] -= 1

    current = 0
    answer = 0

    print("时间点 -> 当前会议室占用数")
    for time in range(n):
        current += diff[time]
        answer = max(answer, current)
        print(f"{time:>4} -> {current}")

    return answer


bookings = [
    [1, 3],
    [2, 4],
    [4, 5],
]

print("最大并发会议数：", max_meeting_rooms(bookings, 6))

运行后可以看到，会议数并不是在每个区间内部重复加一，而是在开始处增加、结束后的下一个位置减少。

复杂度分析 ​

  • 时间复杂度：O(m + n)，其中 m 是会议数量，n 是离散时间点数量；
  • 空间复杂度：O(n)，用于保存差分数组；
  • 相比暴力法的 O(nm)，当区间较长时收益非常明显。

需要注意，LeetCode 一类面试题中的会议室 II 常给出半开区间 [start, end)，即结束时刻房间立即释放。此时结束标记应写在 end，而不是 end + 1。面试时一定要先确认区间语义。

实战二：航班座位占用区间叠加统计 ​

题目模型 ​

航班共有 n 排座位，编号为 1 到 n。每条预订记录为：

text
[first, last, seats]

表示从第 first 排到第 last 排，每排占用 seats 个座位。要求统计每排座位被占用的总数，并判断是否超过飞机容量。

Python 可运行代码 ​

python
def corp_flight_bookings(bookings, n, capacity):
    """
    bookings: [first, last, seats]
    n: 航班排数，编号从 1 开始
    capacity: 每排最大容量
    返回：(每排占用数, 是否超载, 最大占用排)
    """
    # 使用 n + 2，是因为座位编号从 1 开始，last + 1 可能等于 n + 1
    diff = [0] * (n + 2)

    for first, last, seats in bookings:
        diff[first] += seats
        diff[last + 1] -= seats

    occupied = []
    current = 0
    overloaded = False
    max_occupied = -1
    max_row = -1

    for row in range(1, n + 1):
        current += diff[row]
        occupied.append(current)

        if current > capacity:
            overloaded = True

        if current > max_occupied:
            max_occupied = current
            max_row = row

    return occupied, overloaded, (max_row, max_occupied)


bookings = [
    [1, 2, 3],
    [2, 3, 2],
    [3, 5, 4],
]

occupied, overloaded, peak = corp_flight_bookings(
    bookings=bookings,
    n=5,
    capacity=5,
)

print("每排座位占用：", occupied)
print("是否超载：", overloaded)
print("占用最高的排与数量：", peak)

输出结果为：

text
每排座位占用： [3, 5, 6, 4, 4]
是否超载： True
占用最高的排与数量： (3, 6)

这个写法还能自然扩展到“统计多段航线乘客数”。如果把排数换成航程中的离散航段，座位数换成订票人数，就是标准的区间增量统计。

什么时候不能只靠差分数组 ​

差分数组强在离线批处理：先收集全部区间更新，再统一还原。如果业务要求每增加一个预订后，都立刻查询任意时间点的当前值，朴素差分数组无法快速回答前缀和，此时应考虑：

  1. Fenwick Tree / 树状数组：支持单点差分修改和前缀和查询；
  2. 线段树：支持区间增加、区间最大值等更复杂查询；
  3. 事件扫描：只关心最大重叠数且坐标范围很大时，可对 (位置, 变化量) 排序后扫描。

例如会议室问题如果时间戳是完整的 Unix 时间，直接创建覆盖最大值的数组会浪费大量空间。更合适的方法是保存 (start, +1) 与 (end, -1) 事件，再按时间排序扫描。

避坑总结：高频面试题中的边界细节 ​

1. 闭区间和半开区间混用，导致结束点仍被计数 ​

常见错误现象：会议 [1, 3] 在时间点 3 已经结束，但统计结果仍显示占用。原因通常是业务采用半开区间 [start, end)，代码却写成了 diff[end + 1] -= 1。

修正方法：先明确语义。闭区间 [left, right] 使用 right + 1 抵消；半开区间 [left, right) 使用 right 抵消。可以在代码注释和函数文档中固定约定，避免临场出错。

2. 数组长度不足，抵消标记越界 ​

常见错误现象：航班最后一排是第 n 排，执行 diff[last + 1] -= seats 时出现 IndexError。

修正方法：若编号从 0 到 n - 1，数组至少开 n + 1；若编号从 1 到 n，建议开 n + 2。多出来的位置不参与答案，只负责保存边界外的负标记。

3. 坐标很大却直接开数组，造成内存浪费 ​

常见错误现象：时间戳是 1719900000 这种大整数，仍用最大值初始化数组，导致内存暴涨甚至超时。

修正方法：差分数组适合坐标范围可控或已经离散化的场景。坐标稀疏时，应改用事件数组排序扫描，或先进行坐标压缩。不要把“差分数组是 O(n + m)”误解成任何输入都很快，因为这里的 n 是坐标范围，不总是有效点数。

4. 每轮查询都重新前缀还原，退化成重复计算 ​

常见错误现象：每增加一条预订就调用一次完整还原函数，整体复杂度变成 O(mn)，差分优化完全失效。

修正方法：差分数组的最佳使用方式是“收集全部更新，最后还原一次”。如果必须动态查询，应把差分思想迁移到树状数组或线段树上，而不是反复扫描数组。

5. 同位置事件排序错误，导致峰值少算或多算 ​

使用事件扫描时，常见错误是把开始事件和结束事件不加区分地排序。对于半开区间，同一时刻结束后立即开始的会议不应互相冲突；但对于闭区间，结束当天仍可能占用资源。

修正方法：半开区间中，同一位置应先处理结束释放，再处理开始占用；闭区间则应先处理开始，统计峰值后再释放。排序规则必须服务于区间定义，而不是凭感觉写。

结语 ​

差分数组的价值不只是一个模板，而是一种复杂度转换思维：把“对一段连续范围的重复修改”转换成“对边界变化量的记录”。掌握端点约定、数组长度、前缀还原和适用边界后，会议室预订、航班座位、区间加法与资源峰值统计都能稳定落到 O(n + m) 的高效解法上。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

本文来自开发者日记（devdiary.cn）· 记录开发者实战笔记与免费在线工具箱

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。