<aside> ⚠️ 树状数组似乎不能实现：设置区域为某一个值！！而只能增加或减少值！要设置值使用线段树！

</aside>

class BIT:
    """单点修改"""
    def __init__(self, n):
        # [1, n]
        self.tree = [0] * (n + 1) # 树状数组下标从1开始
    
    def add(self, i, delta): # 单点更新：执行+delta
        while i<len(self.tree):
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, left, right): # 区间查询 [left, right]
        return self._query(right) - self._query(left - 1)

    def _query(self, i):  # 前缀和查询
        presum = 0
        while i>0:
            presum += self.tree[i]
            i -= i & (-i)
        return presum

# 例题：<https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/>
class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        bit = BIT(int(1e9 + 10))
        res = 0
        for left, right in tiles:
            bit.add(left, right, 1)
        for left, _ in tiles:
            res = max(res, bit.query(left, left + carpetLen - 1))
        return res

class BIT:
    """范围修改"""

    def __init__(self, n: int):
        self.size = n  # 闭区间[1, n]
        self._tree1 = defaultdict(int)
        self._tree2 = defaultdict(int)

    def add(self, left: int, right: int, delta: int) -> None:
        """闭区间[left, right]加delta"""
        self._add(left, delta)
        self._add(right + 1, -delta)

    def query(self, left: int, right: int) -> int:
        """闭区间[left, right]的和"""
        return self._query(right) - self._query(left - 1)

    def _add(self, index: int, delta: int) -> None:
        rawIndex = index
        while index <= self.size:
            self._tree1[index] += delta
            self._tree2[index] += (rawIndex - 1) * delta
            index += index & -index

    def _query(self, index: int) -> int:
        if index > self.size:
            index = self.size

        rawIndex = index
        res = 0
        while index > 0:
            res += rawIndex * self._tree1[index] - self._tree2[index]
            index -= index & -index
        return res

作者：981377660LMT
链接：<https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/solution/shu-zhuang-shu-zu-by-981377660lmt-rgyz/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<aside> 💡 树状数组的功能是线段树的子集。

</aside>

树状数组的两个基础操作：