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

🕗 发布于 2024-12-29 06:24 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] += val
    d[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 = 0
    while i >= 0:
        ans += d[i]
        i -= 1
    return 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] += val
    d[i2 + 1][j1] -= val
    d[i1][j2 + 1] -= val
    d[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] * n
        for l, r, val in bookings:
            d[l - 1] += val
            if r < n:
                d[r] -= val
        # 计算差分数组的前缀和
        res = [0] * n
        res[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] * n
        for l, r, val in bookings:
            d[l - 1] += val
            if 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] += val
        i += 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 = 0
    while 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 = n
        self.t = [0] * n

    def update(self, i:int, val:int):
        """单点修改"""
        while i < self.n:
            self.t[i] += val
            i += i & -i           # lowbit函数：i & -i。此处未单独设置函数 

    def query(self, i:int):
        """前缀和"""
        ans = 0
        while i > 0:
            ans += self.t[i]
            i -= i & -i           # lowbit函数：i & -i。此处未单独设置函数
        return ans
    

class 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] * n
        for 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)         # 用于维护数组e


def update(i:int, val:int, t:list):
    """树状数组中的单点修改（树状数组维护）"""
    while i <= n:             # 此处，树状数组的长度为n+1，最后一个元素下标为n
        t[i] += val           # t为树状数组
        i += i & -i           # lowbit函数：i & -i，此处未单独设置函数

# 实际维护执行
# 差分数组和数组e的下标都从0开始,树状数组下标从1开始
for i in range(n):
    update(i + 1, d[i], t1)                # 维护差分数组d
    update(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 = 0
    while 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 = n
        self.t = [0] * n

    def update(self, i, val):
        """单点修改（树状数组维护）"""
        while i < self.n:           # 此处，树状数组的长度为n，最后一个元素下标为n-1
            self.t[i] += val
            i += i & -i

    def query(self, i):
        """前缀和，区间[1,i]"""
        ans = 0
        while i > 0:
            ans += self.t[i]
            i -= i & -i
        return 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()
    
    # 差分数组d
    d = [0] * n
    d[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和数组e
    t1 = 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()

执行结果如下：

原文地址：https://blog.csdn.net/yannan20190313/article/details/144592504

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：iPhone 14、iPhone SE 3，提前淘汰
下一篇：【PHP】部署和发布PHP网站到IIS服务器

迅为瑞芯微RK3562开发板/核心板应用于人脸跟踪、身体跟踪、视频监控、自动语音识别(ASR)、图像分类驾驶员辅助系统(ADAS)、车牌识别、物体识别等
iTOP-3562开发板/核心板采用瑞芯微RK3562处理器，内部集成了四核A53+Mali G52架构，主频2GHZ，内置1TOPSNPU算力，RK809动态调频。支持几乎全格式的H.264解码，支
阅读更多2024-12-31
低精度只适用于未充分训练的LLM？腾讯提出LLM量化的scaling laws
尽管有一些研究声称原生的低比特LLM可以媲美fp16/bf16精度下的表现，但这些研究普遍都是在未充分语言模型上得到的结果从而推出的结论，研究人员认为在充分训练的情况下进行比较的话，低比特LLM也将很
阅读更多2024-12-31
医疗数仓配置Flume
Flume需要将Kafka中各topic的数据传输到HDFS，因此选用KafkaSource以及HDFSSink。对于安全性要求高的数据（不允许丢失）选用FileChannel，允许部分丢失的数据如日
阅读更多2024-12-31
Go中CAS算法
CAS算法常被用作乐观锁的实现方式，用于解决并发问题。例如，在计数器、缓存等场景中，可以使用CAS算法来确保数据的一致性和正确性。CAS操作会检查内存位置V的当前值是否与预期的旧值A相等。这一操作是原
阅读更多2024-12-31
Node.js 记账本项目总结
在使用Node.js结合Express框架构建记账本的过程中，遇到了一些常见的问题，这些问题主要集中在路径处理、包管理工具的选择、开发环境优化以及HTTP响应处理等方面。
阅读更多2024-12-31
Java 处理base64文件上传
在系统内有一个类似于公告的模块，如果里面添加的文章不是选择富文本上传图片的方式，而是选择复制别的文章直接粘贴到系统内的富文本，里面的图片就不会url，而是图片的base64格式，这样会导致数据库存储压
阅读更多2024-12-31
Tailwind CSS 实战：现代登录注册页面开发
基础结构搭建表单组件开发社交登录集成响应式适配深色模式支持动画效果表单验证性能优化可访问性增强通过合理使用 Tailwind CSS 的原子类，我们不仅实现了美观的界面，还确保了良好的用户体验和可维护
阅读更多2024-12-31
node.js下载、安装、设置国内镜像源（永久）（Windows11）
系统：Windows 11。
阅读更多2024-12-31
Slate文档编辑器-Decorator装饰器渲染调度
在这里我们主要讨论了slate中的decoration装饰器的实现，以及在实际使用中可能会遇到的问题，主要是在跨节点的情况下，我们需要将range拆分为多个range，然后分别进行处理，并且还分析了源
阅读更多2024-12-31
python去水印
请注意，这种方法仅适用于简单的水印去除，对于复杂的水印或嵌入到图像纹理中的水印，可能无法达到理想的效果。在实际应用中，还可以考虑使用深度学习的方法，如生成对抗网络（GAN）来去除水印，但需要大量的数据
阅读更多2024-12-31

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

差分数组：

差分数组的元素：

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

单点查询（前缀和）：

补充：二维差分数组：

案例：【力扣】

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

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

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

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

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

案例：【力扣】

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

【Python】代码示例：

相关文章