【数据结构】（Python）差分数组。差分数组与树状数组结合

差分数组：

基于原数组构造的辅助数组。
用于区间修改、单点查询。区间修改的时间复杂度O(1)。单点查询的时间复杂度O(n)。
差分数组的元素：第一个元素等于原数组第一个元素，从第二个元素开始是原数组对应下标的元素与前一个元素的差（即原数组相邻元素的差）。
区间修改：通过修改差分数组中区间的两端点，可快速地修改原数组中整个区间的值。具体操作：修改差分数组中起始下标的元素，恢复结束下标的后一个元素。
单点查询：通过差分数组查询原数组中的元素。具体操作：差分数组中从开头到对应下标元素的累和（前缀和）。
注：① 差分与前缀和互为逆运算（差分数组是原数组的差分，原数组是差分数组的前缀和）。② 本文原数组为a，差分数组为d，下标均从0开始。
补充：二维差分数组，类似一维差分数组，注意行和列。
补充：差分数组结合树状数组，可提高效率，也可实现区间修改、区间查询。

差分数组的元素：

差分数组的第一个元素（下标0）：原数组的第一个元素（下标0）。即d[0]=a[0]。
差分数组的下标i 的元素：原数组的下标i 的元素与前一个元素的差。即d[i]=a[i]-a[i-1]。

# a为原数组，d为差分数组
n = len(a)
d = [0] * n        # 差分数组初始化
d[0] = a[0]
for i in range(1, n):d[i] = a[i] - a[i - 1]

区间修改：区间[l,r]

通过修改差分数组中区间的两端点，可快速修改原数组中整个区间的值。

目标：原数组下标l到下标r都修改。例如：区间[l,r]的元素都+val，即a[l]+val，a[l+1]+val，...，a[r]+val。
具体操作：修改差分数组中区间两端点的值，即差分数组下标l修改、下标r+1恢复。例如：d[l]+val，d[r+1]-val。

此处，区间修改由update函数实现。参数：l为区间起始（左侧）下标，r为区间结束（右侧）下标，val为值（例如：增加的值）。

def update(l:int, r:int, val:int):"""区间修改。l为区间起始（左侧）下标，r 为区间结束（右侧）下标，val为值"""d[l] += vald[r + 1] -= val

单点查询（前缀和）：

通过差分数组，查询原数组中的元素。

方法一：前缀和。原数组下标i 的元素为差分数组从下标0到下标i 的元素累和。即a[i]=d[0]+d[1]+...+d[i]。
方法二：原数组下标i 的元素为原数组下标i-1 的元素加上差分数组下标i 的元素。即a[i]=a[i-1]+d[i]。
注：原数组第一个元素等于差分数组第一个元素，即a[0]=d[0]。

此处，单点查询由query函数实现。参数：i为下标。

# 方法一：前缀和
def query(i:int):"""单点查询。i为下标，ans为合计"""ans = 0while i >= 0:ans += d[i]i -= 1return ans# 方法二
a[0] = b[0]
# n为数组长度
for i in range(1, n):a[i] = a[i - 1] + d[i]

补充：二维差分数组：

注：为了便于二维差分数组的理解，此处，二维原数组第一行（行下标0）和第一列（列下标0）的元素均为0。对应二维差分数组的第一行（行下标0）和第一列（列下标0）的元素也均为0。

1、二维差分数组的元素：

# a为二维原数组，d为二维差分数组
n = len(a)            # 矩阵行数
m = len(a[0])         # 矩阵列数
for i in range(1, n):for j in range(1, m):d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

2、二维差分数组的区间修改：

通过修改差分数组矩阵端点的值，修改原数组整个矩阵区间的值。

def update(i1:int, j1:int, i2:int, j2:int, val:int)"""（矩阵）区间修改。(i1,j1)为矩阵起始位置，(i2,j2)为矩阵结束位置"""d[i1][j1] += vald[i2 + 1][j1] -= vald[i1][j2 + 1] -= vald[i2 + 1][j2 + 1] += val

3、二维差分数组的单点查询（前缀和）：

通过差分数组，获取原数组中的元素。

方法一：原数组(i, j)的值为从差分数组开头位置(0, 0)到对应位置(i, j)的所有元素的总和。即a[i][j]=d[0][0]+d[0][1]+...+d[0][j]+d[1][0]+d[1][1]+...+d[1][j]+...+d[i][0]+d[i][1]+...+d[i][j]。
方法二：原数组(i, j)的值为原数组前一行(i-1,j)和原数组前一列(i, j-1)与差分数组中(i, j)的总和。但因原数组(i-1, j)和原数组(i, j-1)两个元素均加上了原数组(i-1, j-1)的值，需减除多加的一次。即a[i][j]=a[i- 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j]。

def query(i:int, j:int, a:list):"""查询原数组的值。i为行下标，j为列下标，a为原数组"""return a[i- 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j]

案例：【力扣】

（难度：中等）1109. 航班预订统计

【Python3】设置差分数组（元素都为0），使用差分数组修改航班区间两端点进行修改整个区间，再计算差分数组的前缀和。

注意：航班编号从1开始，差分数组下标从0开始。

class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:# 差分数组d = [0] * nfor l, r, val in bookings:d[l - 1] += valif r < n:d[r] -= val# 计算差分数组的前缀和res = [0] * nres[0] = d[0]for i in range(1, n):res[i] = res[i - 1] + d[i]return res

可以在差分数组的基础上直接计算前缀和，无需额外占用内存空间开辟新数组。

class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:# 差分数组d = [0] * nfor l, r, val in bookings:d[l - 1] += valif r < n:d[r] -= val# 在差分数组的基础上，直接计算前缀和for i in range(1, n):d[i] += d[i - 1]return d

注：差分数组结合树状数组，可提高效率。题解详见本文“差分数组和树状数组的结合”中的案例。

（难度：困难）1526. 形成目标数组的子数组最少增加次数

【Python3】

解题思路：反向思考，使用差分数组将目标数组的所有元素都变为0。差分数组中的元素都变为0，则对应目标数组的元素也都为0。（因目标数组中的元素是差分数组中元素的前缀和）

根据提示，已知目标数组的元素都为正数，则其差分数组的合计（即目标数组中最后一个元素）一定为正数。
差分数组的第一个元素（即目标数组的第一个元素）也一定为正数。差分数组的其他元素值（差分值）若为负数，则其左侧必定有差分值为正数。
区间修改时，修改差分数组中区间起始下标的值和恢复区间结束下标后一个的值。本题中差分数组的区间起始下标的值减1，区间结束下标后一个的值加1。

本题，统计操作次数即为统计差分值为正数的总和。

若差分值是正数，正数是多少就操作多少次（每次减1），最终变为0。
若差分值为负数，则其左侧的正数差分值减1的同时其会加1，最终变为0，无需统计操作次数。
若正数差分值的合计比负数差分值的合计多，则多的正数差分值减1时，虚拟的(不存在)下标n的值加1。
因差分数组的合计为正数，则不存在负数差分值的合计比正数差分值的合计多。

class Solution:def minNumberOperations(self, target: List[int]) -> int:n = len(target)# 差分数组d = [0] * n       # 差分数组初始化d[0] = target[0]for i in range(1, n):d[i] = target[i] - target[i - 1]# 统计操作次数（统计差分值为正数的总和）ans = 0# 遍历差分数组for i in range(n):# 差分值为正数，则为该元素变为0的操作次数ans += max(d[i], 0)return ans

（简化）可以不额外占用内存开辟差分数组。可以遍历目标数组时，依次计算对应的差分值，并判断且统计操作次数。时间复杂度O(n)，空间复杂度O(1)。

class Solution:def minNumberOperations(self, target: List[int]) -> int:n = len(target)# ans统计操作次数，初始为目标数组第一个元素值ans = target[0]# 从下标1开始遍历目标数组，获取对应下标的差分值for i in range(1, n):# 差分值为正数，则为该元素变为0的操作次数ans += max(target[i] - target[i - 1], 0)return ans

差分数组和树状数组的结合：

差分数组中，区间修改的时间复杂度为O(1)，但单点查询的时间复杂度O(n)。为提高查询的效率，结合树状数组，时间复杂度为O(logn)。

原数组a通过差分获得差分数组d。
通过树状数组t的单点修改（树状数组维护）来维护差分数组d。
使用差分数组的区间修改，而差分数组的区间两端点的修改都通过树状数组的单点修改来完成。
使用树状数组的单点查询（前缀和）获得差分数组的前缀和即原数组中的元素，以此实现差分数组的单点查询。
补充：若再额外维护一个数组e，可使用树状数组的单点查询（前缀和）获取原数组的前缀和，实现区间查询。
注意：原数组a、差分数组d、数组e的下标从0开始，树状数组下标从1开始。

1、差分数组（初始化，维护差分数组的元素）

# 差分数组初始化
n = len(a)
d = [0] * n
# 维护差分数组的元素
d[0] = a[0]
for i in range(1, n):d[i] = a[i] - a[i - 1]

2、树状数组（初始化，维护树状数组的元素）

树状数组下标从1开始，为方便操作，树状数组长度n+1（下标0存在但不使用）。
差分数组下标 i，树状数组下标 i+1。
使用树状数组维护差分数组，此时参数val为差分数组的元素。
即树状数组维护差分数组update(i+1,d[i])。

# 树状数组
n = len(a)
t = [0] * (n + 1)         # 树状数组初始化，下标从1开始(为方便操作，下标0存在但不使用)# 树状数组的单点修改（使用树状数组维护差分数组，因此，val为差分数组的元素）
def update(i:int, val:int):"""树状数组中的单点修改（树状数组维护）"""while i <= n:t[i] += vali += i & -i        # lowbit函数：i & -i，此处未单独设置函数# 实际维护执行
for i in range(n):update(i + 1, d[i])    # 树状数组下标从1开始

3、差分数组的区间修改（通过树状数组的单点修改完成）

差分数组的区间修改，只需修改差分数组中的区间两端点。而此处，区间两端点则都通过树状数组的单点修改完成。

注意下标。

# 差分数组的区间修改：（区间[l,r],修改值val）
# 此处区间为树状数组对应的下标，而差分数组对应区间为[l-1, r-1]
update(l, val)
update(r + 1, -val)

4、树状数组的前缀和（获取原数组中的元素）

通过树状数组的前缀和（区间查询，区间[1,i]）来获得差分数组的前缀和，而差分数组的前缀和为原数组中的元素。

以此实现差分数组的单点查询。

差分数组下标 i，树状数组下标 i+1。

# 树状数组的前缀和（区间查询，区间[1,i]）
def query(i:int):"""树状数组中计算前缀和"""ans = 0while i > 0:ans += t[i]i -= i & -i            # lowbit函数：i & -i，此处未单独设置函数return ans# 实际查询执行
a[i] = query(i + 1)            # 查询原数组中下标i的值

案例：【力扣】

（难度：中等）1109. 航班预订统计

【Python3】差分数组和树状数组结合。即使用树状数组维护差分数组，使用差分数组的区间修改来快速修改整个区间的元素（通过树状数组的单点修改完成），再通过树状数组计算前缀和。

# 类BIT（即树状数组）
class BIT:def __init__(self, n:int):self.n = nself.t = [0] * ndef update(self, i:int, val:int):"""单点修改"""while i < self.n:self.t[i] += vali += i & -i           # lowbit函数：i & -i。此处未单独设置函数 def query(self, i:int):"""前缀和"""ans = 0while i > 0:ans += self.t[i]i -= i & -i           # lowbit函数：i & -i。此处未单独设置函数return ansclass Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:# 使用树状数组维护差分数组（初始元素都为0）bitree = BIT(n + 1)# 差分数组的区间修改（使用树状数组的单点修改完成）for l, r, val in bookings:# 修改差分数组的区间起始的元素bitree.update(l, val)# 恢复区间结束的下一个元素。若区间结束元素是差分数组的最后一个元素，则无需恢复if r < n: bitree.update(r + 1, -val)# 差分数组的前缀和res = [0] * nfor i in range(n):res[i] = bitree.query(i + 1)return res

补充：5、额外维护数组e（可获取原数组的前缀和）

使用两个树状数组分别维护差分数组和数组e，可实现区间修改、单点查询、区间查询。

原数组a通过差分获得差分数组d，并初始化数组e。
使用树状数组分别维护差分数组d和数组e。
区间修改，差分数组的区间两端点的修改都通过树状数组的单点修改来完成。同时数组e的区间也要做相应修改。
使用树状数组的单点查询（前缀和）获得差分数组的前缀和即原数组中的元素，以此实现单点查询。
使用树状数组的单点查询（前缀和）获得原数组的前缀和，以此实现区间查询。

因：原数组的前缀和：s[i] = a[0] + a[1] +...+ a[i]

差分数组的前缀和（原数组的元素）：a[i] = d[0] + d[1] +...+ d[i]

因此：s[i] = a[0] + a[1] +...+ a[i]

= d[0] + (d[0] + d[1]) + ...+ (d[0] + d[1] +...+ d[i])

= (i+1)* (d[0] + d[1] +...+ d[i]) - (0 * d[0] + 1 * d[1] + ...+ i * d[i])

= $eq?%28i%20+%201%29%20*%20%5Csum%20d%5Bi%5D%20-%20%5Csum%20i%20*%20d%5Bi%5D$

其中， $eq?%5Csum%20d%5Bi%5D$ 为差分数组的前缀和，则维护额外的数组e（元素为 i * d[i]），获取数组e的前缀和。

注意：原数组a和差分数组d和数组e下标从0开始。而树状数组下标从1开始，注意实际对应下标。

（5-1）差分数组d和数组e的初始化，以及维护差分数组元素

# 差分数组d和数组e初始化，a为原数组
n = len(a)
d = [0] * n
e = [0] * n# 维护差分数组元素
d[0] = a[0]
for i in range(1, n):d[i] = a[i] - a[i - 1]

（5-2）两个树状数组的初始化，以及使用树状数组维护差分数组d和数组e

两个树状数组分别用于维护差分数组（元素d[i]）和数组e（元素 i * d[i]）。
差分数组和数组e下标 i，树状数组下标 i+1。

# 两个树状数组初始化
n = len(a)
t1 = [0] * (n + 1)         # 用于维护差分数组d
t2 = [0] * (n + 1)         # 用于维护数组edef update(i:int, val:int, t:list):"""树状数组中的单点修改（树状数组维护）"""while i <= n:             # 此处，树状数组的长度为n+1，最后一个元素下标为nt[i] += val           # t为树状数组i += i & -i           # lowbit函数：i & -i，此处未单独设置函数# 实际维护执行
# 差分数组和数组e的下标都从0开始,树状数组下标从1开始
for i in range(n):update(i + 1, d[i], t1)                # 维护差分数组dupdate(i + 1, d[i] * i, t2)            # 维护数组e

（5-3）差分数组的区间修改（使用树状数组的单点修改完成）

树状数组区间[l,r]，树状数组修改下标 l 和下标 r+1。
即差分数组和数组e对应区间[l-1, r-1]，差分数组和数组e中对应修改下标 l-1 和下标 r。
注意：数组e的元素为d[i]*i。差分数组修改的同时，数组e也修改，且数组e的修改值需乘以对应下标 i 。

# 差分数组的区间修改（使用树状数组的单点修改完成），区间[l,r]
# 树状数组下标从1开始,原数组和差分数组和数组e下标从0开始。
# 此处区间为树状数组对应的下标，而差分数组和数组e对应区间为[l-1, r-1]
update(l, val, t1)
update(r + 1, -val, t1)
update(l, val * (l - 1), t2)       # 树状数组下标为l，而数组e对应下标为l-1
update(r + 1, -val * r, t2)        # 树状数组下标为r+1，而数组e对应下标为r

（5-4）前缀和（获取原数组中的元素，以及获取原数组的前缀和）

通过树状数组获取差分数组的前缀和，差分数组的前缀和为原数组中的元素，即a[i] = d[0]+d[1]+...+d[i]。
通过树状数组获取原数组的前缀和，即 $eq?s%5Bi%5D%20%3D$ $eq?%28i%20+%201%29%20*%20%5Csum%20d%5Bi%5D%20-%20%5Csum%20i%20*%20d%5Bi%5D$ ，此公式 i 从0开始。
原数组下标 i，树状数组下标 i+1。

def query(i:int, t:list):"""树状数组中计算前缀和"""ans = 0while i > 0:ans += t[i]           # t为树状数组i -= i & -i           # lowbit函数：i & -i，此处未单独设置函数return ans# 树状数组下标从1开始，原数组和差分数组和数组e下标从0开始
# 实际获取原数组的值
for i in range(n):a[i] = query(i + 1, t1)# 实际获取原数组的前缀和
for i in range(n):s[i] = (i + 1) * query(i + 1, t1) - query(i + 1, t2)

（5-5）区间和（获取原数组的区间和）

获取原数组的区间[l,r]的元素和，即s[l,r]=s[r]-s[l-1]。

因树状数组下标从1开始，原数组下标从0开始。对应树状数组的区间为[l+1,r+1]。

def range_query(l:int, r:int):"""获取原数组的区间[l,r]的元素和，s[l,r]=s[r]-s[l-1]"""# 原数组下标从0开始，树状数组下标从1开始。树状数组对应区间[l+1,r+1]return (r + 1) * query(r + 1, t1) - query(r + 1, t2) - (l * query(l, t1) - query(l, t2))

具体的树状数组知识点：树状数组

【Python】代码示例：

注：原数组a、差分数组d、数组e的下标从0开始，树状数组下标从1开始。

# 类BIT（即树状数组）
class BIT:def __init__(self, n):self.n = nself.t = [0] * ndef update(self, i, val):"""单点修改（树状数组维护）"""while i < self.n:           # 此处，树状数组的长度为n，最后一个元素下标为n-1self.t[i] += vali += i & -idef query(self, i):"""前缀和，区间[1,i]"""ans = 0while i > 0:ans += self.t[i]i -= i & -ireturn ans# 主程序
def main():a = [5,2,6,1,7,9]n = len(a)# 打印原数组的元素print(f"原数组：                ", end="")for i in range(n):print(a[i], end="    ")print()# 差分数组dd = [0] * nd[0] = a[0]for i in range(1, n):d[i] = a[i] - a[i - 1]# 打印差分数组的元素print(f"差分数组：              ", end="")for i in range(n):print(d[i], end="    ")print()# 数组e（元素：d[i] * i）e = [0] * n# 使用树状数组维护差分数组d和数组et1 = BIT(n + 1)t2 = BIT(n + 1)for i in range(n):t1.update(i + 1, d[i])t2.update(i + 1, d[i] * i)# 假设：原数组区间[1,3]都加10，修改差分数组的树状数组和数组e的树状数组# 树状数组对应区间[2,4]t1.update(2, 10)            # （差分数组）修改区间起始下标的元素t1.update(5, -10)           # （差分数组）修改区间结束下标的后一个元素t2.update(2, 10 * 1)        # （数组e）修改区间起始下标的元素t2.update(5, -10 * 4)       # （数组e）修改区间结束下标的后一个元素# 打印修改后原数组中所有元素（即差分数组的前缀和）print(f"修改后差分数组的前缀和：", end="")for i in range(n):a[i] = t1.query(i + 1)print(a[i], end="    ")print()# 获取原数组中下标2的元素print(f"原数组中下标2的元素：{a[2]}")# 打印修改后数组e的前缀和print(f"修改后数组e的前缀和：   ", end="")for i in range(n):e[i] = t2.query(i + 1)print(e[i], end="    ")print()# 获取原数组中下标2的前缀和print(f"修改后原数组的前缀和：  ", end="")s = [0] * n                # 记录原数组的前缀和for i in range(n):s[i] = (i + 1) * t1.query(i + 1) - t2.query(i + 1)print(s[i], end="    ")print()print(f"原数组中下标2的前缀和：{s[2]}")# 获取原数组中区间和，区间[2,5]rq = s[5] - s[1]print(f"原数组中区间和,区间[2,5]：{rq}")# 主程序执行
main()

执行结果如下：