python实现树状数组的区间修改并给出案例

树状数组（Fenwick Tree）是一种用于维护序列前缀和的数据结构，可以支持单点修改和区间查询。在树状数组中，每个节点存储的是前缀和的增量。具体来说，节点 i 存储的是原始序列中 i 的子序列的和与 i 的父节点对应的子序列的和之间的差值。这样，在查询时，沿着节点的父链前缀和的差值就可以得到区间和。

下面给出 Python 实现树状数组的区间修改的代码：

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def query(self, i):
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query_range(self, l, r):
        return self.query(r) - self.query(l - 1)

    def update_range(self, l, r, delta):
        self.update(l, delta)
        self.update(r + 1, -delta)

这里实现了单点修改、区间查询和区间修改三种操作。其中，update_range(l, r, delta) 函数用于对区间 [l, r] 中的所有元素加上 delta。

下面给出一个使用树状数组实现区间修改的例子。假设有一个长度为 n 的序列，初始时所有元素均为 0。有 m 次操作，每次操作输入三个数 l、r 和 delta，表示将区间 [l, r] 中的所有元素加上 delta。

n, m = map(int, input().split())
A = [0] * (n + 1)
BIT = FenwickTree(n)

for _ in range(m):
    l, r, delta = map(int, input().split())
    BIT.update_range(l, r, delta)

for i in range(1, n + 1):
    A[i] = BIT.query(i)

print(*A[1:])

该程序首先构造一个长度为 n 的初始值均为 0 的列表 A 和一个对应的树状数组 BIT。然后，对于每次操作，调用 BIT.update_range(l, r, delta) 函数对区间 [l, r] 中的所有元素加上 delta。最后，再遍历一遍整个序列，用 BIT.query(i) 函数计算前缀和得到最终的结果。