一、差分数组是什么？

差分数组是一种用于高效处理区间更新和查询的技术，特别适用于需要频繁对数组的某个区间进行加减操作，并且在操作后查询某些位置或区间的值的问题。
定义为相邻两项的差：

如何构造差分数组

代码实现：

# 定义差分数组
diff = [0] * (n + 1)
diff[0] = a[0]
for i in range(1, n):
    diff[i] = a[i] - a[i - 1]

• 1
• 2
• 3
• 4
• 5

二、差分数组的作用

给定区间 [ l, r ]，让我们把数组中的[ l, r ] 区间中的每一个数加上c,即 a[ l ] + c , a[ l + 1 ] + c , a[ l + 2] + c , a[ r ] + c;
怎么做呢？
暴力做法：for循环 l到r 区间，时间复杂度O(n)
有更快的做法吗? 有的，兄弟有的。——使用差分算法。

数组中的[ l, r ] 区间中的每一个数都加上c,只需要对差分数组做 b[ l ] + = c, b[ r+1 ] - = c 。
时间复杂度为O(1)
最后对差分数组做前缀和还原成原数组
如何计算前缀和，可以查看我的博客，点此进入http://iyenn.com/rec/1618853.html?spm=1001.2014.3001.5501

如何还原成原数组

对 差分数组 做前缀和可以还原成 原数组 ；
差分即为前缀和的逆运算。

# 对差分数组求前缀和进行还原
a[0] = diff[0]
for i in range(1, n):
    a[i] = a[i - 1] + diff[i]

• 1
• 2
• 3
• 4

实战演练1： 区间更新

点此进入题目页面https://www.lanqiao.cn/problems/3291/learning/?page=1&first_category_id=1&name=%E5%8C%BA%E9%97%B4%E6%9B%B4%E6%96%B0

思路分析：

注意点：输入有多组数据，但未给出数据组数——对输入进行处理，进行异常捕获

题解：

while True:
    try:
        n, m = map(int, input().split())
        a = list(map(int, input().split()))
        
        # 定义差分数组
        diff = [0] * (n + 1)
        diff[0] = a[0]
        for i in range(1, n):
            diff[i] = a[i] - a[i - 1]

        for _ in range(m):
            x, y, z = map(int, input().split())
            x -= 1
            y -= 1  # 题目中x，y下标从1开始
            diff[x] += z
            diff[y + 1] -= z

        # 对差分数组求前缀和进行还原
        a[0] = diff[0]
        for i in range(1, n):
            a[i] = a[i - 1] + diff[i]
        print(' '.join(map(str, a)))
    except:
        break

• 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

实战演练2： 小明的彩灯

点此进入题目页面https://www.lanqiao.cn/problems/1276/learning/?page=1&first_category_id=1&problem_id=1276

思路分析：

注意点：彩灯亮度为负 输出 0 必须在最后处理 否则会影响后缀还原为原数组

题解：

n, q = map(int, input().split())
a = list(map(int, input().split()))
diff = [0] * (n + 1)
diff[0] = a[0]
for i in range(1, n):
    diff[i] = a[i] - a[i - 1]
for _ in range(q):
    l, r, x = map(int, input().split())
    l -= 1
    r -= 1
    diff[l] += x
    diff[r + 1] -= x
a[0] = diff[0]
for i in range(1, n):
    a[i] = diff[i] + a[i - 1]
for i in range(n):
    if a[i] < 0:
        a[i] = 0
print(' '.join(map(str, a)))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20