動機

當初看binary index tree看了很久，要記錄一下

binary index tree

tree的樣子

build

因為是prefix sum所以如果從底部往上建，就是把目前建好的node往上一層送

像是1~1就是1~2的前半部，1~4就是1~2與3~3

那要怎麼決定要往那一個地方送? 這就是特別的地方了，往n+lowbit(n)

lowbit定義成離左邊(最低位)最近的第一個1，像

  • lowbit(1) => 1
  • lowbit(2) => 2
  • lowbit(3) => 1

因為每次往上都是遞增一個lowbit(n)，所以很像list

def __init__(self,arr):
    self.n = len(arr)
    self.bit = [0] * (1+self.n)
    
    for (i,n) in enumerate(arr):
        i += 1 # bit start from 1
        self.bit[i] += n
        nextI = i + (i&(-i)) # lowbit(i)
        if nextI <= self.n:
            self.bit[nextI] += self.bit[i]

update

剛剛的build是從底往上，update也是所以兩個很像

def update(self,i,diff):
    while i <= self.n:
        self.bit[i] += diff
        i += (i&(-i))

query

build與update都是往上加lowbit(n)，query可以類推成扣lowbit(n)? 對

def query(self,n): # [1..n]
    ret = 0
    while n > 0:
        ret += self.bit[n]
        n -= (n&(-n))
    return ret

為什麼是lowbit?

從lowbit去看每個區間會發現lowbit(n)到左邊(最低位)的距離就是會有幾個區間要加，像

  • lowbit(1) => 0 (就是自己)
  • lowbit(2) => 1 (1~1與自己)
  • lowbit(4) => 2 (1~2與3~3與自己)

還有lowbit(n)到左邊(最低位)的range，如果有1可以看成有幾個node，像

  • 1~5 => 101，1~4與5~5
  • 1~7 => 111，1~4與5~6與7~7

從這裡也可以看出來，為什麼bit的query是1~n，因為是透過binary去看有幾個1去加總

所以，bit就是利用binary來表示有幾個區間的prefix sum tree

Ref

這應該是最好懂bit的資料