树状数组（时间复杂度On）：常用于处理动态数组的前缀和/区间和查询和单点更新

leetcode原题链接：https://leetcode.cn/problems/range-sum-query-mutable/description/?envType=daily-question&envId=2023-11-13

class Fenwick:
    __slots__  = 'tr', 'n'

    def __init__(self, n):
        self.n = n
        self.tr = [0] * n

    def lowbit(self, x) -> int:
        return x & -x
    # 把下标为 i 的元素增加 c
    def update(self, x: int, c: int) -> None:
        while x < self.n:
            self.tr[x] += c
            x += self.lowbit(x)
    # 返回下标在 [1,i] 的元素之和
    def prefixSum(self, x: int) -> int:
        res = 0
        while x > 0:
            res += self.tr[x]
            x -= self.lowbit(x)
        return res

    def sumRange(self, left: int, right: int) -> int:
        return self.prefixSum(right + 1) - self.prefixSum(left)