树形数组

总结背景介绍 lowBit函数单点元素修改求区间和模板题目速通参考

树形数组擅长的题目是 修改单点元素 + 区间求和。每一步操作都是logn

当然，也可以用左区间更新，单点查询，此时只需要将原始数组转化为差分数组即可！

难点在于怎么从题目中挖掘出来，抽象出来要使用树形数组。就是不好想！

树状数组的规律分享和leetcode315题(超级详细适合小白，第一个视频中Tree数组应该是真实存在的，说错了）_哔哩哔哩_bilibili

总结

树状数组的题目不好想，想到了就直接上模板即可！

首先记住根本：新创建的数组tree[idx]是原数组 nums在区间 [idx-lowbit(idx)-1:idx] 的范围和。这个区间长度为lowbit(x)。

然后记住初始化，单点更新，区间查询的模板即可。

初始化：

背下来吧（要是记不住们可以没有初始化，直接用update函数，只不过时间复杂度为nlog(n)）


tree = [0] + nums[:]
for i in range(1, len(tree):
		j = i + lowbit(i)
		if j < len(len(tree)):
				tree[j] += tree[i]

单点更新：

需要更新改下标所在树状数组中有关的分段。那怎么判断是否有关呢？假设更新原始数组下标d的值，我需要更新树状数组下标 [d+1]的值，还需要更新 d+1 + lowbit(d+1) 的值，再这样迭代更新上去。

区间查询：

要算区间 [k1, k2] 和，只需要计算[1, k1-1] 和 [1,k2]这两个区间和，然后[k1, k2] = [1, k2] - [1, k1-1] 。

背景

正常一个线性数组的修改元素的时间复杂度为O(1)，求区间和的时间复杂度为O(right-left)，最坏的时间复杂度为O(n)(即从1到n之间进行累加)

而如果用前缀和数组，那么修改某个某个元素的时间复杂度变成O(n) (即在前缀和数组中,从这个元素后面的所有元素都得更新)。而求区间和的时间复杂度则为O(1)

显然，上面两种办法修改元素和查询区间和的时间复杂度无法得到一个比较好的平衡，而这时候有个叫树形数组的数据结构可以非常好地应对这么个情况。

树形数组可以使得：

修改元素时间复杂度O(logn)

区间和查询时间复杂度O(logn)

树状数组（Binary Indexed Tree, 又Fenwick Tree）其实并不是一棵树，只是对数组各元素进行逻辑上的划分。根据维基百科，树状数组是一种用于高效计算数组前缀和的数据结构，它可以以O(logn)的时间得到任意前缀和（两个前缀和相减即可得到区间和），并同时支持以O(logn)的时间对数组某个值进行修改，空间复杂度为O(n)。

介绍

从英文名字Binary Indexed Tree可猜到树状数组是与二进制有关的，事实上确实是这样，树状数组的核心思想就是将一个前缀和划分成多个子序列的和，而划分的方法与2的幂（或者说二进制）密切相关。

具体如下：

树状数组将原数组分为多个段，然后直接存放这些段的区间和。具体的分段方式如下：

[R-lowbit(R)+1, R]，即每个段的长度为 lowbit（R）。原数组和分段数组各自代表含义如下：

可见：

对于奇数来说，lowbit 肯定是 1 ,所以下标为奇数的段只是原数组该下标的和

长度为 n 的数组最多会被分为 log(n)段，所以说每个操作的时间复杂度都是 log(n)

树状数组c[x] 表示原始数组区间 a[x-lowbit(x)+1 :x]之和，（写为左开右闭区间即为 (x-lowbit(x), x]）

那如何快速计算树状数组的各个值呢？

参见下图，如果要计算c[16],那么最快应该是 c[16] = c[8] + c[12] + c[14] + c[15] + a[16]

15 是 16 - 1得到的，

14 是 15 - lowbit(15) 得到的，

12 是 15 - lowbit(15) 得到的，

8 是 12 - lowbit(12) 得到的，

之后 8 - lowbit(b) = 0 就不再计算了

此时已经有树的模样了。

lowBit函数

可以用来获取某个二进制数的LowBit(即截出最后一个1及其后面的bit)


def lowbit(x):
		return x & (-x)

单点元素修改

单点元素修改时，需要顺带修改该点到根节点的所有值。即找到所在结点，然后用lowBit函数依次自下而上更新其所有父结点

例如，要更新 a[4] 时，需要更新 c[4], c[8], c[16] 等，知道下标大于范围


结合上图： 
当更新A[1]时(设新的A[1]比原来增加了d),需要自下向上更新C[1],C[2],C[4],C[8]

写为二进制：C[(001)],C[(010)],C[(100)],C[(1000)]
 
lowBit(1)=001   1+lowBit(1)=2(010)     C[2]+=d
lowBit(2)=010   2+lowBit(2)=4(100)     C[4]+=d
lowBit(4)=100   4+lowBit(4)=8(1000)    C[8]+=d

总结规律：即找到1所在结点，然后用lowBit函数依次自下而上更新其所有父结点

求区间和

Range(i,j)就是闭区间[i,j]的区间和。策略是用区间 [1, j] 和减去区间和 [1, i-1]。那区间和 [1, i]怎么求呢？从当前段开始，逐渐累加之前各个分段的和，之前的分段怎么算呢？用当前的下标 - lowbit即可


for k in range(i, 0, -1): 
		sum_ += tree[i]     
		i -= lowbit(i)


以求5-7之间的区间和为例，设区间和presum:

先求1-7之间的和，即7的前缀和。

                     7(111)            presum+=C[7]
lowBit(7)=001    7-lowBit(7)=6(110)    presum+=C[6]
lowBit(6)=010    6-lowBit(6)=4(100)    presum+=C[4]
lowBit(4)=100    4-lowBit(4)=0(000) 

总结规律：找到7所在结点，用lowBit函数不断消去最后一个1，并进行累加

再求1-5之间的和。

                     5(101)            presum+=C[5]
lowBit(5)=001    5-lowBit(5)=4(100)    presum+=C[4]
lowBit(4)=100    4-lowBit(4)=0(000) 

最后将两个前缀和相减就得到区间和了。

模板


'''BIT：Binary Indexed Tree 树状数组'''
class NumArray:
    
    '''自定义lowbit函数'''
    def lowbit(self, x: int) -> int:
        return x&(-x)

    def __init__(self, nums: List[int]):
        self.tree = [0] + nums              # 构造出的BIT空间比原nums多一，第1个下标0不用
        for i in range(1, len(self.tree)):  # 这种方式构造的BIT时间复杂度为O(n)
            j = i + self.lowbit(i)          # 构造BIT的巧妙方式
						# 父节点 加上子节点 的值
            if j < len(self.tree):
                self.tree[j] += self.tree[i]

    def update(self, index: int, val: int) -> None:
        pre_val = self.sumRange(index, index)   # index：在原nums中的位置
        delta = val - pre_val                   # 变更值
        i = index + 1                           # i: 对应数值在BIT中的位置（index+1）
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)

    '''自定义前缀和preSum函数'''
    def preSum(self, index: int) -> int:    # index：在原nums中的位置
        i = index + 1                       # i: 对应数值在BIT中的位置（index+1）
        summ = 0
        while i:
            summ += self.tree[i]
            i -= self.lowbit(i)            # 这里 i -=lowbit(i),是下降到子节点
  
        return summ
    
    def sumRange(self, left: int, right: int) -> int:
				# [left, right] 是闭区间 
        return self.preSum(right) - self.preSum(left-1)   # right对应的前缀和



#************************保留原数组的方式

class NumArray:
    def lowbit(self, x):
        return x & (-x)

    def __init__(self, nums: List[int]):
        # 原数组
        self.nums = nums
        # 树状数组
        self.tree = [0] * (len(self.nums) + 1)
        # 构建树状数组
        for i in range(1, len(self.tree)):
            self.tree[i] += self.nums[i-1]
            # i + self.lowbit(i) 为 父节点的下标
            # 父节点 = nums的值 + 子节点的值
            if i + self.lowbit(i) < len(self.tree):
                self.tree[i + self.lowbit(i)] += self.tree[i] 

    def update(self, index: int, val: int) -> None:
        # 如果相同就不用改了
        if val == self.nums[index]:
            return
        
        i = index + 1
        delta = val - self.nums[index]
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)
        # 修改原数组
        self.nums[index] = val

    def prefix(self, index):
        i = index + 1
        sum_ = 0
        while i > 0:
            sum_ += self.tree[i]
            i -= self.lowbit(i)
        
        return sum_       


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