Open in app

Sign in

Write

Sign in

Algorithms & Data Structures : 區間問題集錦 ( 4 ) — Binary Indexed Tree ( Fenwick Tree)

吳建興
23 min readMay 8, 2022

--

Hello!

本篇延續了上一篇的內容。

本篇主要是參考 ( 抄襲 ) 這個大神的筆記。
假如看到內容有錯誤的話，再麻煩跟我說一聲了~

Binary Indexed Tree ( BIT )

單點修改
建構 BIT
前綴和查詢
例題：leetcode 307 Range Sum Query — Mutable ( 單點修改，查詢區間和 )
BIT + 差分序列
BIT + 差分序列：O( logN ) 區間修改
BIT + 差分序列：建構 BIT
BIT + 差分序列：O( logN ) 單點查詢
BIT + 差分序列：區間查詢
例題：ZeroJudge d799 ( 區間加值，查詢區間和 )
動態開點 BIT
例題：LeetCode : 493. Reverse Pairs
高維 BIT
高維 BIT：單點修改
高維 BIT：高維 BIT 建構
高維 BIT：區間查詢
例題：308. Range Sum Query 2D — Mutable
例題：面試考古題

Binary Indexed Tree ( Fenwick Tree)

Binary Indexed Tree 的索引由 1 開始。假設原始陣列為

A = [a_1, a_2, a_3, a_4];
A[1] == a_1; // 陣列的索引由 1 開始

且 lowbit 代表該數字的最低位 bit 所代表的值

#define LOWBIT(x) ((x) & -(x))8 == b1000
LOWBIT(8) == 8
11 = b1011
LOWBIT(11) == 1
10 = b1010
LOWBIT(10) == 2

則 binary indexed tree 在索引 i 的意義為範圍 [ i-LOWBIT(i) + 1, i ] 的值。
令 binary indexed tree 為 int BIT[16]; (1-indexed，索引值由 1 開始)。

BIT[2] → 代表原陣列的索引 [1, 2] 這個區間的值
BIT[6] → 代表原陣列的索引 [5, 6] 這個區間的值
BIT[16] → 代表原陣列的索引 [1, 16] 這個區間的值

e.g.

int A[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
BIT[2] = A[1] + A[2];
BIT[6] = A[5] + A[6];
BIT[16]= A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] + A[9] + A[10] + A[11] + A[12] + A[13] + A[14] + A[15] + A[16];

單點修改

void __modify(int pos, int diff, vector<int> &bit) {
    for(;pos < bit.size();pos += LOWBIT(pos)) {
      bit[pos] += diff;
   }
}

每當我們加上 LOWBIT(pos)時，就會往兄弟節點移動。走到最後一個兄弟節點時，若再加上 LOWBIT(pos) ，就會到達父母節點的兄弟節點。

當我們想要修改一個節點的值時，我們需要連帶修改所有包含該值的區間。以下圖為例，我們想要修改原陣列索引值為 9 的節點 ( A[9] ) ，則我們需要連帶修改 BIT[9], BIT[10], BIT[12], BIT[16]。

假如我們想要修改原陣列索引值為 3 的節點 ( A[3] ) ，則我們需要連帶修改 BIT[3], BIT[4], BIT[8], BIT[16]。

有趣的是，我們只要不斷的增加 LOWBIT(pos) ， 就能遍尋所有我們需要修改的節點！

建構 BIT

我們只需要一個個將原陣列的元素，用單點修改的方式填入 BIT 即可。

void initialize(vector<int> &orig, vector<int> &bit) {
   for(int i = 0;i < orig.size();i++) {
      __modify(i + 1, orig[i], bit);
   }
}}

pos — LOWBIT(pos) 會是 pos 的父母節點。
想要取得以 pos 為結尾的前綴和，只需要一路往父母節點的方向加過去即可。

int query(int pos, vector<int> &bit) {
   pos += 1;
   int res = 0;
   for(;pos >= 1;pos -= LOWBIT(pos)) {
      res += bit[pos];
   }
   return res;
}

例如我們想要取得原陣列 1~3 的區間和，我需要加上 BIT[3] + BIT[2]
{ 3 — LOWBIT(3) == 2 }

例如我們想要取得原陣列 1~3 的區間和，我需要加上 BIT[15] + BIT[14] + BIT[12] + BIT[8]
{15} ==> [15, 15]
{ 15— LOWBIT(15) == 14} ==> [13, 14]
{ 14 — LOWBIT(14) == 12} ==> [9, 12]
{ 12— LOWBIT(12) == 8} ==> [1, 8]
{ 8— LOWBIT(8) == 0} ==> 到此結束
[15, 15] + [13, 14] + [9, 12] + [1, 8] == [1, 15]

前綴和查詢

#define LOWBIT(x) (x & -x)class NumArray {
private:
    vector<int> orig;
    vector<int> bit;
    
    // 實際去修改 BIT
    void __modify(int pos, int diff, vector<int> &bit) {
        for(;pos < bit.size();pos += LOWBIT(pos)) {
            bit[pos] += diff;
        }
    }    // 單點修改
    void modify(int pos, int val, vector<int> &orig, vector<int> &bit) {
        int diff = val - orig[pos];
        orig[pos] = val;
        pos += 1;
        __modify(pos, diff, bit);
        
    }    // 前綴和查詢
    int query(int pos, vector<int> &bit) {
        pos += 1;
        int res = 0;
        for(;pos >= 1;pos -= LOWBIT(pos)) {
            res += bit[pos];
        }
        return res;
    }    // initialize a BIT
    void initialize(vector<int> &orig, vector<int> &bit) {
        for(int i = 0;i < orig.size();i++) {
            __modify(i + 1, orig[i], bit);
        }
    }public:
    NumArray(vector<int>& nums) {
        orig = nums;
        bit = vector<int>(orig.size() + 1, 0);
        initialize(orig, bit);    
    }
   
    // 進行單點修改
    void update(int index, int val) {
        modify(index, val, orig, bit);
    }
 
    // 使用前綴和去取得區間和
    int sumRange(int left, int right) {
        if(left == 0) {
            return query(right, bit);
        }
        return query(right, bit) - query(left - 1, bit);
    }
};

BIT + 差分序列

原本的 BIT 並沒有支援區間修改的功能，但是我們可以將 BIT 的概念與差分序列的概念融合，讓我們可以讓 BIT 也支援區間修改的功能。

在差分序列，已知使用前綴和可得真實的元素值。
e.g.

// 原陣列
int a[] = {3, 1, 5, 6};
// 差分序列
int d[] = {3, -2, 4, 1};
--> 依序取其前綴和，會得到原陣列
int dPreFixSum = {3, 1, 5, 6};

那原陣列的前綴和該怎麼以差分序列來表示呢？
在這一篇文章，大神給出了一個式子。

a_i 代表原陣列的第 i 個元素。
D_i 代表差分序列的第 i 個元素。

可以發覺，想要取得原陣列的前綴和，需要下列兩個陣列的前綴和

所以只需要兩個 BIT ，一個維護 D_i 的前綴和，另外一個維護 D_i * i 的前綴和，就可以算出原陣列的前綴和。

至此，我們可以用差分序列的特性，在區間修改時，只需要修改左節點以及右節點 + 1 的位置，共兩個位置。在 BIT 裡，像這樣單點修改的時間複雜度為 O(logN)。

並且只需要利用 BIT ， 則可在 O(logN) 得前綴和，所以區間查詢的時間複雜度也為 O(logN)

BIT + 差分序列：O( logN ) 區間修改

// dv, dv2 的索引值從 0 開始
// bitdv, bitdv2 的索引值從 1 開始// dv 為 D_i, dv2 為 D_i * i
// bitdv  為 dv  的 BIT
// bitdv2 為 dv2 的 BIT#define LL long long
#define LOWBIT(x) (x & -x)using namespace std;void __modify(LL pos, LL diff, vector<LL> &bit) {
   for(;pos < bit.size();pos += LOWBIT(pos)) {
      bit[pos] += diff;
   }
}void modify(LL pos, LL diff, vector<LL> &bit) {
   pos += 1;
   __modify(pos, diff, bit);
}// 需要修改差分序列 dv 以及 dv2 的 left 以及 right + 1 的位置
// 並且在修改 dv, dv2 以前，需要先修改相對應的 bitdv, bitdv2
void interval_modify(LL left, LL right, LL val, vector<LL> &dv, vector<LL> &dv2, vector<LL> &bitdv, vector<LL> &bitdv2) {   // 修改 left 的 bitdv, bitdv2
   modify(left, val, bitdv);
   modify(left, (dv[left] + val) * (left + 1) - dv2[left], bitdv2);   // 修改 right + 1 的 bitdv, bitdv2
   if(right + 1 < dv.size()) {
      modify(right + 1, -1 * val, bitdv);
      modify(right + 1, (right + 2) * (dv[right + 1] - val) - dv2[right + 1], bitdv2);
   }   // 修改 left 的 dv, dv2
   dv[left] += val;
   dv2[left] = (left + 1) * dv[left];   // 修改 right + 1 的 dv, dv2
   if(right + 1 < dv.size()) {
      dv[right + 1] -= val;
      dv2[right + 1] = (right + 2) * dv[right + 1];
   }
}

BIT + 差分序列：建構 BIT

   // 原陣列
   for(int i = 0;i < n;i++) {
      cin >> inv[i];
   }   vector<LL> dv  = vector<LL>(inv.size(), 0);
   vector<LL> dv2 = vector<LL>(inv.size(), 0);   // 利用原陣列去算出差分序列
   dv[0] = inv[0];
   dv2[0] = inv[0];
   for(int i = 1;i < n;i++) {
      dv[i] = inv[i] - inv[i - 1];
      dv2[i] = dv[i] * (i + 1);
   }   vector<LL> bitdv  = vector<LL>(inv.size() + 1, 0);
   vector<LL> bitdv2 = vector<LL>(inv.size() + 1, 0);   // 初始話 bitdv, bitdv2
   // initialize bit
   for(int i = 0;i < inv.size();i++) {
      modify(i, dv[i], bitdv);
      modify(i, dv2[i], bitdv2);
   }

BIT + 差分序列：O( logN ) 單點查詢

實作跟原本的 BIT 一模一樣，可以很快地拿到某個 BIT 的前綴和。

LL query(LL pos, vector<LL> &bit) {
   pos += 1;
   LL res = 0;
   for(;pos >= 1;pos -= LOWBIT(pos)) {
      res += bit[pos];
   }
   return res;
}

BIT + 差分序列：區間查詢

取得前綴和之後，再利用剛剛所講的公式，就可以求得原陣列的前綴和。
有了前綴和之後，就可以拿到區間和。

LL interval_sum(LL left, LL right, vector<LL> &bitdv, vector<LL> &bitdv2) {
   LL res = 0;   LL sumLeft1 = 0;
   LL sumLeft2 = 0;
   if(left > 0) {
      sumLeft1 = query(left - 1, bitdv);
      sumLeft2 = query(left - 1, bitdv2);
   }   LL sumRight1 = query(right, bitdv);
   LL sumRight2 = query(right, bitdv2);   // left 原本是 0-indexed,
   //   + 1 後變成 1-indexed
   //   再 + 1 使其變成 x + 1
   LL sumLeft = sumLeft1 * (left - 1 + 2) - sumLeft2;
   LL sumRight = sumRight1 * (right + 2) - sumRight2;   res = sumRight - sumLeft;
   return res;
}

例題：ZeroJudge d799 ( 區間加值，查詢區間和 )

#include <cstdio>
#include <iostream>
#include <vector>

#define LL long long
#define LOWBIT(x) (x & -x)

using namespace std;

void __modify(LL pos, LL diff, vector<LL> &bit) {
   for(;pos < bit.size();pos += LOWBIT(pos)) {
      bit[pos] += diff;
   }
}

void modify(LL pos, LL diff, vector<LL> &bit) {
   pos += 1;
   __modify(pos, diff, bit);
}

void interval_modify(LL left, LL right, LL val, vector<LL> &dv, vector<LL> &dv2, vector<LL> &bitdv, vector<LL> &bitdv2) {
   modify(left, val, bitdv);
   modify(left, (dv[left] + val) * (left + 1) - dv2[left], bitdv2);
   if(right + 1 < dv.size()) {
      modify(right + 1, -1 * val, bitdv);
      modify(right + 1, (right + 2) * (dv[right + 1] - val) - dv2[right + 1], bitdv2);
   }

   dv[left] += val;
   dv2[left] = (left + 1) * dv[left];

   if(right + 1 < dv.size()) {
      dv[right + 1] -= val;
      dv2[right + 1] = (right + 2) * dv[right + 1];
   }
}

LL query(LL pos, vector<LL> &bit) {
   pos += 1;
   LL res = 0;
   for(;pos >= 1;pos -= LOWBIT(pos)) {
      res += bit[pos];
   }
   return res;
}

LL interval_sum(LL left, LL right, vector<LL> &bitdv, vector<LL> &bitdv2) {
   LL res = 0;

   LL sumLeft1 = 0;
   LL sumLeft2 = 0;
   if(left > 0) {
      sumLeft1 = query(left - 1, bitdv);
      sumLeft2 = query(left - 1, bitdv2);
   }

   LL sumRight1 = query(right, bitdv);
   LL sumRight2 = query(right, bitdv2);

   // left 原本是 0-indexed,
   //   + 1 後變成 1-indexed
   //   再 + 1 使其變成 x + 1
   LL sumLeft = sumLeft1 * (left - 1 + 2) - sumLeft2;
   LL sumRight = sumRight1 * (right + 2) - sumRight2;

   res = sumRight - sumLeft;

   return res;
}

int main(int argc, char *argv[]) {
   LL n;
   cin >> n;
   vector<LL> inv = vector<LL>(n);

   for(int i = 0;i < n;i++) {
      cin >> inv[i];
   }

   vector<LL> dv  = vector<LL>(inv.size(), 0);
   vector<LL> dv2 = vector<LL>(inv.size(), 0);

   dv[0] = inv[0];
   dv2[0] = inv[0];
   for(int i = 1;i < n;i++) {
      dv[i] = inv[i] - inv[i - 1];
      dv2[i] = dv[i] * (i + 1);
   }

   vector<LL> bitdv  = vector<LL>(inv.size() + 1, 0);
   vector<LL> bitdv2 = vector<LL>(inv.size() + 1, 0);

   // initialize bit
   for(int i = 0;i < inv.size();i++) {
      modify(i, dv[i], bitdv);
      modify(i, dv2[i], bitdv2);
   }

   cin >> n;
   for(int i = 0;i < n;i++) {
      int op;
      cin >> op;
      if(op == 1) {
         LL left;
         LL right;
         LL val;

         cin >> left;
         cin >> right;
         cin >> val;

         left -= 1;
         right -= 1;

         interval_modify(left, right, val, dv, dv2, bitdv, bitdv2);

      } else if(op == 2) {
         LL left;
         LL right;

         cin >> left;
         cin >> right;

         left -= 1;
         right -= 1;

         LL res = interval_sum(left, right, bitdv, bitdv2);
      }
   }

   return 0;
}

動態開點 BIT

線段樹可以動態開點，在範圍過大時，不要一開始就初始化全部的元素。 BIT 也可以做到類似的操作，範例可以看一下接下來的例題！

例題：LeetCode : 493. Reverse Pairs

效能可以說是相當的差，需要再想想辦法提升效能。

#define LL long long
#define BASE 2147483649LL
#define MAXVAL (BASE * 2)
#define LOWBIT(x) ((x) & (-x))class Solution {
private:
    unordered_map<LL, int> bit;
    
    void modify(LL pos, LL val) {
        for(LL i = pos;i <= MAXVAL;i += LOWBIT(i)) {
            bit[i] += val;
        }
    }
    
    LL query(LL pos) {
        LL tmp = 0;
        for(LL i = pos;i > 0;i -= LOWBIT(i)) {
            tmp += bit[i];
        }
        return tmp;
    }
    
public:
    int reversePairs(vector<int>& nums) {
        int res = 0;
        for(LL i = 0;i < nums.size();i++) {
            res += (query(MAXVAL) - query(((LL)nums[i] * 2 + BASE)));
            modify(nums[i] + BASE, 1);
        }
        
        return res;
    }
};

高維 BIT

BIT 如同線段樹一樣，也能夠處理高維度的資料。

高維 BIT：單點修改

   void modify(int x, int y, int val) {
        x += 1;
        y += 1;
        int diff = val - input[x][y];
        
        input[x][y] = val;
        for(int i = x;i < bit.size();i += LOWBIT(i)) {
            for(int j = y;j < bit[0].size();j += LOWBIT(j)) {
                bit[i][j] += diff;
            }
        }
    }

高維 BIT：高維 BIT 建構

        bit = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        input = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        
        for(int i = 0;i < matrix.size();i++) {
            for(int j = 0;j < matrix[0].size();j++) {
                modify(i, j, matrix[i][j]);
            }
        }

高維 BIT：區間查詢

   int prefixSum(int row, int col) {
        int res = 0;
        for(int i = row;i >= 1;i -= LOWBIT(i)) {
            for(int j = col;j >= 1;j -= LOWBIT(j)) {
                res += bit[i][j];
            }
        }
        return res;
    }    int query(int row1, int col1, int row2, int col2) {
        row1 += 1;
        col1 += 1;
        row2 += 1;
        col2 += 1;        int A = prefixSum(row2, col2);
        int B = prefixSum(row2, col1 - 1);
        int C = prefixSum(row1 - 1, col2);
        int D = prefixSum(row1 - 1, col1 - 1);
        return A - B - C + D; 
    }

例題：308. Range Sum Query 2D — Mutable

#define LOWBIT(x) ((x) & (-x))class NumMatrix {
private:
    vector<vector<int>> bit;
    vector<vector<int>> input;
    
    void modify(int x, int y, int val) {
        x += 1;
        y += 1;
        int diff = val - input[x][y];
        input[x][y] = val;
        for(int i = x;i < bit.size();i += LOWBIT(i)) {
            for(int j = y;j < bit[0].size();j += LOWBIT(j)) {
                bit[i][j] += diff;
            }
        }
    }
    // 取得某一個 row, col 範圍內的前綴和    
    int prefixSum(int row, int col) {
        int res = 0;
        for(int i = row;i >= 1;i -= LOWBIT(i)) {
            for(int j = col;j >= 1;j -= LOWBIT(j)) {
                res += bit[i][j];
            }
        }
        return res;
    }
    // 利用前綴和去取得區間和 
    int query(int row1, int col1, int row2, int col2) {
        row1 += 1;
        col1 += 1;
        row2 += 1;
        col2 += 1;
        
        int A = prefixSum(row2, col2);
        int B = prefixSum(row2, col1 - 1);
        int C = prefixSum(row1 - 1, col2);
        int D = prefixSum(row1 - 1, col1 - 1);
        return A - B - C + D; 
    }
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        bit = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        input = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
   
       // 建構 BIT   
       for(int i = 0;i < matrix.size();i++) {
            for(int j = 0;j < matrix[0].size();j++) {
                modify(i, j, matrix[i][j]);
            }
        }   
    }
    
    void update(int row, int col, int val) {
        modify(row, col, val);
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row1, col1, row2, col2);
    }
};

例題：面試題

初始化時，會給定一個陣列。
現在希望能支援兩種操作：

  1. 單點修改
  2. 輸入x 找出，第一個 a 使得h[0]+h[1]+…h[a]>x

這個問題可以輕易地使用 binary indexed tree 解決。

第一個需求，單點修改的部分，可以在 O( logN ) 的時間複雜度解決。

第二個需求，可以對前綴和進行二分搜，每搜一次需要 O(logN) ， 於是可以取得 O((logN) * (logN)) 的時間複雜度。

Bye!

終於學習完 binary Indexed Tree 了，接下來會找許多練習題來練習這個資料結構的運用 XD

Reference

  1. 區間問題概述 — 這篇太厲害了!
  2. Segment tree & Lazy Propagation
  3. 大神的線段樹筆記
  4. wikipedia : 線段樹
  5. 建國中學，演算法講義 : 線段樹詳解
  6. 資訊之芽算法班
  7. 資訊之芽
    https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree.pdf
    https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree_2.pdf
    https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/Segment_Tree_inclass.pdf
  8. draw.io : 好用的畫圖網站
Algorithms
Leetcode
Binary Indexed Tree

--

--

吳建興
吳建興

Written by 吳建興

42 Followers
49 Following

I want to be a good programmer.(´・ω・`)

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams