Python差分算法详解与实践

系列文章目录

Python高效处理区间更新的神器：一维与二维差分算法详解

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言

差分算法作为数值计算的基础工具，在科学计算、工程应用和机器学习中具有广泛用途。理解其数学原理并掌握高效的 Python 实现方法，能够帮助开发者在处理实际数据时更灵活地选择合适的差分策略。

提示：以下是本篇文章正文内容，下面案例可供参考

一、差分算法核心思想

1.1 什么是差分数组

差分数组(diff array)是一种通过对原数组相邻元素差值进行编码的数据结构。给定数组a[1..n]，其差分数组定义为：

diff[1] = a[1]
diff[i]=a[i]-a[i-1]
diff[2] =a[2] -a[1]
diff[3] =a[3]-a[2]
diff[n]=a[n]-a[n-1]

对差分数组做前缀和可以还原为原数组：

diff[1]+ diff[2]+ diff[3]+...+diff[i]
= a[1] + (a[2]- a[1]) + (a[3]- a[2])+... +(a[]- a[i - 1])
=a[i]

1.2 差分数组的优势

二、一维差分数组实战

2.1 区间加法原理

当对原数组区间[l, r]执行加x操作时：

diff[l] += x
diff[r+1] -= x  # 若r+1越界则无需操作

数学证明​​：
前缀和计算时，x将从l位置开始持续作用到数组末尾，通过r+1位置的-x抵消后续影响

差分数组可以实现快速的区间加法，最终只需要对差分数组求前缀和
就能得到原数组
无法边修改边查询，只能先修改，后查询
diff[]]+=x：相当于从l往后全部的数字都加上x
diff[r+1]-=x：相当于从r+1往后全部数字都减去x

以蓝桥杯的一道习题为例：https://www.lanqiao.cn/problems/3291/learning/

while True:
    try:
        # 读取数组长度n和操作次数m
        n, m = map(int, input().split())
        # 读取原始数组a
        a = list(map(int, input().split()))
        # 构建差分数组diff，长度为n+1，方便处理区间操作
        diff = [0] * (n + 1)
        # 初始化差分数组第一个元素，对应原始数组第一个元素
        diff[0] = a[0]
        # 构建差分数组：diff[i] = a[i] - a[i-1]，表示a中第i个元素与前一个元素的差
        for i in range(1, n):
            diff[i] = a[i] - a[i - 1]
        # 处理m次区间操作
        for _ in range(m):
            # 读取操作参数x, y, z（表示对区间[x, y]加上z）
            x, y, z = map(int, input().split())
            # 将输入的1-based索引转换为0-based索引
            x, y = x - 1, y - 1
            # 差分数组处理区间加z：在x位置加上z，在y+1位置减去z，这样通过前缀和能实现区间更新
            diff[x] += z
            diff[y + 1] -= z
        # 对差分数组求前缀和，恢复原始数组a
        a[0] = diff[0]
        for i in range(1, n):
            a[i] = a[i - 1] + diff[i]
        # 输出最终处理后的数组，元素用空格连接
        print(' '.join(map(str, a)))
    except:
        # 捕获异常（如输入错误等），退出循环
        break

三、二维差分数组进阶

3.1 二维差分公式推导

差分数组的前缀和=原数组

因此先回顾二维数组前缀和：

sum(i,j)= sum(i-1,j) + sum(i,j-1)- sum(i-1,j-1)+ a(i,j)

上述的sum替换成a，a替换成diff，就可以得到二维差分数组：

diff(i,j)=a(i,j) -a(i-1,j)-a(i,j-1) +a(i-1,j-1)

3.2二维差分数组的实现

def output(a, n):
    """
    输出二维数组a的函数
    :param a: 二维数组，行下标从1到n，列下标从1到m
    :param n: 二维数组的行数（有效行数）
    """
    for i in range(1, n + 1):
        # 打印每一行从第2个元素开始的所有元素（因为第1个元素是初始的0，这里展示实际输入数据部分）
        print(' '.join(map(str, a[i][1:])))

# 读取输入的两个整数n和m，n表示行数，m表示列数
n, m = map(int, input().split())

# 初始化二维数组a，行下标从0到n（实际使用1到n），列下标从0到m（实际使用1到m），初始值为0
# 这样设计下标从1开始方便后续计算（符合某些算法习惯）
a = [[0] * (m + 1) for i in range(n + 1)]
# 初始化二维差分数组diff，结构与a相同
diff = [[0] * (m + 1) for i in range(n + 1)]

# 输入二维数组a的内容
# 循环读取n行数据，每行m个整数
for i in range(1, n + 1):
    # 在每行数据前添加一个0，使列下标从1开始（前面0作为占位）
    a[i] = [0] + list(map(int, input().split()))
# 调用output函数输出原始二维数组a（每行从第2个元素开始是实际输入数据）
output(a, n)

# 计算二维差分数组diff
# 双重循环遍历每个有效元素（行1到n，列1到m）
for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 二维差分公式：diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
        # 这个公式用于构建二维数组的差分数组，以便后续区间操作
        diff[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]
# 调用output函数输出二维差分数组diff（每行从第2个元素开始是实际差分数据）
output(diff, n)

3.3 矩阵区域操作

当对子矩阵(x1,y1)-(x2,y2)执行加x操作时：

diff[x1][y1] += x
diff[x2+1][y1] -= x
diff[x1][y2+1] -= x
diff[x2+1][y2+1] += x

结语：当数据遇见差分——算法之美与无限可能

在本文的探索旅程中，我们揭开了差分算法从一维到二维的数学面纱

通过差分数组的精妙设计，我们成功将区间操作的时间复杂度从O(n)压缩至O(1)，这种以空间换时间的哲学思辨，正是算法工程师突破性能瓶颈的经典范式就像快速排序的分治智慧（O(n log n)时间复杂度）与哈希算法的瞬间定位（O(1)查找）差分算法再次证明：​​优雅的数学建模往往比暴力计算更具革命性​​。

最后分享一个程序员箴言​​：差分数组就像时间旅行者——它记录变化而非状态，这正是爱因斯坦相对论在代码世界的微观映射。当你在处理海量数据时，愿这份「变化捕捉术」助你游刃有余，在算法的星辰大海中，发现更多简洁而强大的数学之美。

作者：弦思李工