树状数组学习

树状数组（Binary Indexed Tree，BIT）

• 也称为Fenwick树
• 二叉索引树
• 是一种常见的数据结构，可以高效地处理数组的前缀和和区间修改。树状数组可以支持单点修改、前缀查询以及区间查询等操作，时间复杂度均为 $O(logn)$。

主要解决两个操作：

• 前缀和查询
• 单点更新

虽然这个操作线段树也能够解决（甚至线段树还能解决其他问题），但是线段树的速度与树状数组差了常数倍

树状数组结构、新建缓存方式如下所示


然后呈现如下规律

为什么要引入lowbit操作？是为了快速求出$2^k$
其中，k是从右往左数，第一个1的右边有几个0的数量

lowbit(i) = i & (-i)

然后顺着树走就可以，例如：

• 求A1-A7的和：即C7（0111）+C6（0110）+C4（0100）
• 求A1-A5的和：即C5（0101）+C4（0100）
  看出规律了么？就是这么简单

V1-基础实现

python代码：
注意 下标要从1开始

class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 1)]

    def __lowbit(self, index):
        return index & (-index)

    # 单点更新：从下到上，最多到 size，可以取等
    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += self.__lowbit(index)

    # 区间查询：从上到下，最少到 1，可以取等
    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.__lowbit(index)
        return res

V2-离散化

离散化技巧：
当取值区间过于巨大而数本身很稀少（稀疏）的时候，就可以把数本身换成排序完成以后的下标（即相对顺序）

# 离散化：绝对数值转秩次
uniques = sorted(set(nums))
rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】

V3-RMQ

RMQ树状数组
求区间最大+单点更新
原理没有仔细理解，先码上

class MaxFenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [-100000 for _ in range(n + 1)]
        self.a = []

    def __lowbit(self, index):
        return index & (-index)

    # 单点更新：从下到上，最多到 size，可以取等
    def update(self, index, val):
        self.tree[index] = val
        i = 1
        while i < self.__lowbit(index):
            self.tree[index] = max(self.tree[index], self.tree[index - i])
            i = i << 1

    # 区间查询：从上到下，最少到 1，可以取等
    def query(self, l,r):
        res = self.a[r]
        if l == r:
            return self.a[r]
        while l <= r:
            res = max(res,self.a[r])
            r -= 1
            while r-l >= self.__lowbit(r):
                res = max(res, self.tree[r])
                r -= self.__lowbit(r)
        return res

题目：

待填