RMQ怎么实现树状数组区间更新

树状数组（Fenwick Tree）是一种高效的数据结构，常用于处理动态前缀和查询和单点更新。然而，树状数组本身并不直接支持区间更新操作。为了实现区间更新，我们可以结合RMQ（Range Minimum Query）的思想，对树状数组进行扩展。

实现思路

1. 差分数组：首先，我们引入差分数组的概念。对于原数组A，我们定义差分数组D，其中D[i] = A[i] - A[i-1]（假设A[0] = 0）。这样，区间更新[l, r]加上val可以转化为对差分数组D[l] += val和D[r+1] -= val。

2. 树状数组维护差分：我们使用树状数组来维护差分数组D。这样，单点更新和前缀和查询都可以在O(log n)时间内完成。

3. 区间更新：对于区间[l, r]的更新操作，我们只需要在树状数组中对D[l]和D[r+1]进行更新即可。具体来说，update(l, val)和update(r+1, -val)。

4. 查询操作：查询某个位置i的值时，可以通过树状数组的前缀和查询sum(i)来得到A[i]的值。

代码示例

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)

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

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

    def range_update(self, l, r, val):
        self.update(l, val)
        self.update(r + 1, -val)

    def point_query(self, idx):
        return self.query(idx)

总结

通过引入差分数组和树状数组的结合，我们可以在O(log n)时间内实现区间更新和单点查询。这种方法不仅高效，而且代码实现简单，适用于需要频繁进行区间更新的场景。