【lc刷题】307 区域和检索 - 数组可修改(BIT)_Day19(68/300)

68/300

307. 区域和检索 - 数组可修改
     给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
      
     update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
      
     示例:
      
     Given nums = [1, 3, 5]
      
     sumRange(0, 2) -> 9
     update(1, 2)
     sumRange(0, 2) -> 8
      
     说明:
      
     数组仅可以在 update 函数下进行修改。
     你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

有update，使用 binary indexed tree(BIT)/ fenwick tree

303 区域和检索 - 数组不可变&304 二维区域和检索 - 矩阵不可变都是用的dp，存前面所有range的和，

而bit就是存部分range的和，一旦遇到update，就不需要迁一发动全身啦，而是动部分身，像这样：

说白了，就是每个节点都有一个管控范围：

为了构建这样的效果，我们需要用到二进制（起始位置从2⁰开始，而不是从0开始）。

来看1+2+3+…+16 = 136 如何用BIT储存：

这样的tree我们是如何建立的？

移动都是一个一个的，十进制的步长是1，二进制的步长是整串数最右的1
譬如，
十进制的6，下一个是6+1 = 7
二进制的6，表示为(0110)₂，找到最右边的1，也就是(0010)₂，
(0110)₂+(0010)₂=(1000)₂，相当于十进制的8，看上图，6的下一个节点是8
同理，二进制的4和7，下个节点也都是8
节点8的值就是4，6，7三个节点的和。

当树建好后，我们要问问题了，前8个数的和是多少？

这时候要往前看，看节点8之前还有没有不在它的管控范围下的节点

8: (1000)₂ - (1000)₂ = 0，也就是节点8自己的值就够了

按此(超出控制范围的节点)重新构造树，再看一眼节点8（控制范围1~8），前面没有超管控范围的节点）。

如果求前7个数的和，也就是节点7的值（控制范围7自己）+节点6的值（控制范围5~6）+节点4的值（控制范围1~4）

用代码表示：Python位运算符（二进制）

get rightmost set bit:
x & -x

add rightmost set bit:（找上级，用于构造树）
x += x & -x 

remove rightmost set bit:（用于查找前面超管控范围的节点）
x -= x & -x 

def prefix_sum(BIT, i):
  result = 0
  while i > 0:
    result += BIT[i]
    i -= i & -i #查找管控范围外的节点
  return result

prefix_sum时间复杂度：O(log(n))

def update(BIT, i, diff):
  while i < len(BIT):
    BIT[i] += diff
    i += i & -i #去往下一个相关节点

update时间复杂度：O(log(n))

How do we actually initialize the BIT? One simple approach is that you initialize BIT with all zeros, and for each element in the array you call UPDATE. However, because every call to UPDATE takes O(log(n)) time, the total runtime of building BIT is O(nlog(n))。

RANGE_SUM(i, j)=PREFIX_SUM(j)−PREFIX_SUM(i-1)

class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        self.nums = [0]*n
        self.bit = [0]*(n+1) #多了一个dummy
        for i in range(n):
            self.update(i, nums[i])

    def update(self, i: int, val: int) -> None:
        diff, self.nums[i] = val-self.nums[i], val
        j = i+1
        while j < len(self.bit):
            self.bit[j] += diff
            j += j&(-j)       
    
    def sumRange(self, i: int, j: int) -> int:
        
        def _sum(i):
            j = i+1
            total = 0
            while j > 0:
                total += self.bit[j]
                j -= j &(-j)
            return total
        
        return _sum(j) - _sum(i-1)

文章参考：
https://www.sungwoncho.me/posts/binary-indexed-tree

BIT讲解：
https://www.youtube.com/watch?v=CWDQJGaN1gY
https://www.youtube.com/watch?v=v_wj_mOAlig
https://www.youtube.com/watch?v=4SNzC4uNmTA
https://www.youtube.com/watch?v=kPaJfAUwViY