Introduct

vector<int> nums = {1, 5, -2, 7, 4, 3, 6, 2};
如果要求 range sum，例如 sum(1, 5) = 17
有兩種operation，1. 求某個range的和，2. update每個一值。
如果使用vector，和prefix sum，分別的time complexity如下:

	update	getSum
vector	$O(1)$	$O(N)$
prefix-sum	$O(N)$	$O(1)$

如果是update非常頻繁，但是求和的情況非常少，可以使用vector。
相反的，
如果是update很少，但是求和的情況非常頻繁，就可以使用prefix-sum。

如果是update和求和都很頻繁，那就必須要用binary index tree，

	update	getSum
BIT	$(logN)$	$O(logN)$

Reference

1. Binary Indexed Tree or Fenwick Tree

Binary Index Tree

1. 使用N-ary tree，parent和child只相差一個bit。

2. 使用dummy node(index 0)，不儲存任何資料
   

3. child存放的數值，是到parent的總和(不包括parent)。例如: index-12 = nums[9] + nums[10] + nums[11] + nums[12]。
   

4. getSum(index)，計算從0 ~ index的總和。就是從一路從index加到root。例如: sum(0 ~ 13) = bit(13) + bit(12) + bit(8);
   

因為是tree的走訪，所以time complexity =

$O(logN)$

5. update element, 必須update有儲存此index的項目。例如update n[5]，必須同時update bit[5], bit[6]和bit[8]

Code Snippet

getSum()

從BIT中計算0 ~ index的總和。

int getSum(int idx) {
    ++idx; // 轉換成在BIT中使用的index
    int sum = 0;
    while(idx > 0) {// 因為index 0為dummy node
        sum += BIT[idx];
        idx -= idx & -idx; // 往parent移動，每次都減掉left most set bit
    }
    return sum;
}

update()

更新某個vector中的數值，因為n[i]已經加起來了，所以只能增減n[i]的數值。

// 這邊的val是新舊n[idx]的差值。
// val = n'[idx] - n[idx]
void update(int idx, int val) {
    ++idx; // 轉換成在BIT中使用的index
    // sz為vector的大小，因為BIT長度多1，所以使用小於等於
    while(idx <= sz) { 
        BIT[idx] += val;
        idx += idx & -idx;
    }
}

Construct the BIT

從一個vector<int> nums建立一個BIT。

vector<int> nums = {1, 5, -2, 7, 4, 3, 6, 2};
int sz = nums.size();
// 因為多一個dummy node, 預設所有值都為0 
vector<int> BIT(sz + 1); 
for(int i = 0; i < sz; ++i)
    update(i, nums[i]);

2D BIT

ref : Fenwick Tree/Binary Indexed Tree (BIT)

vector<vector<int>> nums;
int m = nums.size();
int n = nums[0].size();

和1D BIT一樣，使用長寬都大1的2D vector來儲存。

vector<vector<int>> bit(m + 1, vector<int>(n + 1));
// construct the 2D BIT
void construct(vector<vector<int>>& nums)
{
for(int y = 0; y < m; ++y)
    for(int x = 0; x < n; ++x)
        update(y, x, nums[y][x]);
}                       

update function

void update(int y, int x, int diff) 
{
    y++; x++;
    for(int i = y; i >= m; i += i & -i) {
        for(int j = x; j >= n; j += j & -j) {
            bit[i][j] += diff;
        }
    }    
}

calculate range sum function

int getSum(int y, int x) {
    int sum = 0;
    y++; x++;
    for(int i = y; i > 0; i -= i & -i)
        for(int j = x; j > 0; j -= i & -i)
            sum += bit[i][j];
    return sum;
}
int getRangeSum(int top, int left, int bottom, int right) {
    return getSum(bottom, left) - 
           getSum(top - 1, right) - 
           getSum(bottom, left - 1) + 
           getSum(top - 1, left - 1);    
}

計算個數

把value當成index

BIT可以用來計算range sum，如果反過來使用把數值當成index, value改為個數，則可計算比目前數值大或小的個數。

例如315. Count of Smaller Numbers After Self

nums = [5,2,6,1]

因為0為dummy node，所以index = nums[i] + 1
當idx = 0, nums[0] = 5, index = 5 + 1 = 6往右看如下

index	0	1	2	3	4	5	6★	7
value			1	1				1

則range sum(1, 5)即為小於nums[0] = 5的個數。

Problems

307. Range Sum Query - Mutable

題目很明顯就是要實現Binary index tree。

class NumArray {
    vector<int> nums;
    vector<int> bit;
    int sz;
    void updateBIT(int idx, int val) {
        ++idx;
        while(idx <= sz) {
            bit[idx] += val;
            idx += idx & -idx;
        }
    }
    int getSum(int idx) {
        ++idx;
        int sum = 0;
        while(idx > 0) {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
public:
    NumArray(vector<int>& nums) {
        // 儲存原本的vector，才可以計算diff
        this->nums = nums;
        sz = nums.size();
        bit.resize(sz + 1);
        for(int i = 0; i < sz; ++i)
            updateBIT(i, nums[i]);
    }
    
    void update(int index, int val) {
        updateBIT(index, val - nums[index]);
        // 必須把val記錄起來，才可以算出正確的diff
        nums[index] = val;
    }
    
    int sumRange(int left, int right) {
        // left == 0, left - 1 = -1，
        // 但是在BIT中，index會修正為0
        // 所以可以正常使用
        return getSum(right) - getSum(left - 1);
    }
};

406. Queue Reconstruction by Height

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    int sz = people.size();
    auto cmp = [&](vector<int>& a, vector<int>& b) {
        if(a[0] < b[0]) return true;
        else if(a[0] == b[0]) return a[1] > b[1];
        else return false;           
    };   
        
    // method : binary index tree
    //          binary index tree 求 0 ~ n 的合 tc = O(logN), update其中一個數 tc = O(logN)
    //          一開始要知道前面有幾個空位 input vector = [0, 1, 1, 1, ... 1]
    //                                   sum          = [0, 1, 2, 3, ... n - 1] <-- 使用BIT表示
    //          當有一個數值被填入之後，空格減少           [0, 1, 1, 0, ... 1]
    //                                   sum          = [0, 1, 2, 2, ....n - 2] <-- 使用BIT表示
    sort(people.begin(), people.end(), cmp);
    vector<vector<int>> rtn(sz, vector<int>());
    vector<int> bit(sz + 1);
    auto update = [&](int idx, int val) {
        idx++;
        while(idx <= sz) {
            bit[idx] += val;
            idx += idx & -idx;
        }    
    };
    auto getsum = [&](int idx) -> int {
        int sum = 0;
        idx++;
        while(idx > 0) {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    };
    // input array [0, 1, 1, 1, ..., 1]
    for(int i = 1; i < sz; ++i) update(i, 1); 
    for(auto& p : people) {
        int left = 0, right = sz; // 因為有可能是sz - 1
        while(left < right) {
            int mid = left + (right - left) / 2;
            int sum = getsum(mid);
            //  if p[1] == 3;
            //  因為是要取3 的第一個
            //  left/mid(<)  right(>=)
            //   2,          3
            if (sum >= p[1]) right = mid;
            else left = mid + 1;
        }
        rtn[left] = p;
        update(left, -1); // 空格子減少
    }
    // time : O(NlogN) + O(N * logN)
    return rtn;
}

315. Count of Smaller Numbers After Self

給你一個vector<int> nums, 回傳右邊比目前的數還小的個數。

1. 使用BIT來計算比目前的數還小的個數。

class BIT{
    vector<int> v;
public:
    // 多一個長度是因為index = 0為dummy node
    BIT(int n) : v(n + 1){}
    void update(int idx, int val) {
        // 因為小值為-1e4，如果只加 1e4則idx = 0 為dummy node
        // 所以改加 1e4 + 1
        idx += 1e4 + 1;
        while(idx < v.size()) {
            v[idx] += val;
            idx += idx & -idx;
        }
    }
    int query(int idx) {
        // 因為是找比自己還小的數，所以不用加1
        idx += 1e4;
        int rtn = 0;
        while(idx > 0) {
            rtn += v[idx];
            idx -= idx & -idx;
        }
        return rtn;
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int sz = nums.size();
        BIT bit(2e4 + 1); // 因為從-1e4到1e4的長度為2e4 + 1(包括0)。
        vector<int> rtn(sz);
        bit.update(nums.back(), 1);
        for(int i = sz - 2; i >= 0; --i) {
            rtn[i] = bit.query(nums[i]);
            bit.update(nums[i], 1);
        }
        return rtn;
    }
};

tags: leetcode 刷題