Binary Index Tree

Introduction

Binary Index Tree (BIT)是一種資料結構，通常的使用情景為程式需要以下操作時:

• 區間查詢
• 單點修改

舉例來說:

• 題目要求須要能處理以下兩種 Query 需求:
  • Query 1: 找出位於[l, r]的區間和
  • Query 2: 修改位於idx的值 ，變成val

Note: 若單純只需要查詢區間值，而不需要改值，可以改用 Prefix Array

Examples

BIT實際上是一個陣列，而為了瞭解實際陣列內實際存的值，可以把BIT的概念圖畫出來

上圖中的數字代表BIT的index，也就是當存取bit[2]時，實際的值如上圖的框框所示，代表[1, 2]區間的值。

舉例來說，假設BIT存的是區間和，並且Input array為: [3, 1, 5, 1, 2, 6, 10, 2]

把該array建成BIT(1-index based)後會長成如下圖:

• E.g. bit[2]代表區間[1, 2]的加總，因此是3 + 1 = 4

有了BIT的概念後，假設想要求

• [1, 5]的區間和，可以發現答案為: bit[5] + bit[4] = 12
• 想要單點修改index: 5的值，只需要修改包含該index的區間就好，而這些區間為: bit[5], bit[6], bit[8]

---

現在問題變成，如何知道要修改哪些區間的值?

• 觀察BIT結構，可以發現想要查詢區間值時，會從原本的值不斷往左上方搜尋，直到結束為止。

• 而觀察數字之間的關係，可以發現跟low bit (數字轉成binary後從右邊數來第一個為1的bit) 有關

  • 假設想找區間和，bin(5) => 101, lowbit為1。想要往左上方搜尋，把5減掉lowbit 5 - 1 = 4 就好了。
  • 假設想更新值，bin(5) => 101, lowbit為1。想要往上方去做更新，把5加上lowbit 5 + 1 = 6 就好了。

• lowbit的求法為: x & -x，也就是數字跟其二補數做 & 操作。

Time Complexity

• Query: $O(log\thickspace n)$
• Update: $O(log\thickspace n)$

Different Types of Problems

視不同題目的需求，可能的應用場景也不一樣

• Leetcode 2736
  • 題目需要區間求Maximum，但是區間只會是 [x, tail], tail為最右邊的值。
  • 改值時，不需要清掉舊的值，而是跟舊的值比大小
  • 因此，這題可以使用BIT來做

Implementation

了解概念後，實作就很簡單了。

以下實作為求區間和及單點加值的BIT:

Initialize

int M = 100005;
vector<int> bit(M);

Update

若要做到單點改值，而不是單點加值，則在修改前需要先Query找出原本值為何，接著算出之間的差值後就可以變成單點加值的操作了。

void update(int x, int val) {
    while(x < M) {
        bit[x] += val;
        x += (x & -x);
    }
}

Query

void query(int x) {
    int sum = 0;
    while(x) {
        sum += bit[x];
        x += (x & -x);
    }
    return sum;
}