Skip to content

樹狀數組 (Bit Index Tree, BIT)

支援單點修改的區間和查詢

給定一個長度為 的序列 和 筆操作，有兩種操作：

  • 1 x v：將 加上 。
  • 2 x y：詢問 之間的和。

支援修改及查詢區間訊息的題目可以用線段樹實作，然而比線段樹容易實作的樹狀數組也可解決這類問題。樹狀數組只需要一個長度為 的陣列 ， 的每一個位置存放的資料和編號有關：

  • 存放 到 的資訊。
  • ，為 在二進位下的最低為 的位數。
  • 節點 的父節點為 ，父節點有子節點的資訊。

lowbit 計算原理

整數 的二補數，是先把 的二進位中 01 互換，再加上 得來的。將 和 相比，大於 的每一位數，如果 是 ，在 會是 ，如果 是 ，在 會是 ；小於 的每一位數，在 和 都會是 ；只有 所對應的位數在 和 都會是 。因此 的結果會是 。下面以 為例。

單點修改

單點修改 ，需更新所有包含 的資訊，從 開始，依序更新 和 的所有祖先。

1
2
3
4
5
6
7
8
void update(int i)
{
    while (i < N)
    {
        ++BIT[i];
        i += lowbit(i);
    }
}

會不斷增加，在二進位下，每次至少會右移一位，一次查詢的時間複雜度為 。

區間查詢

區間查詢 到 的資訊，從 獲得 到 的資訊，再到 獲得下一個區間的資訊，以此類推。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int query(int i)
{
    int ans = 0;
    while (i)
    {
        ans += BIT[i];
        i -= lowbit(i);
    }
    return ans;
}

會不斷減少，在二進位下，每次會將最低為 的位數變成 ，一次修改的時間複雜度為 。

應用

可用來維護可修改的區間和與區間積查詢，不支援區間極值查詢。

  • 的區間和（積）可由 和 的區間和（積）相減（除）求得。
  • 和 的區間極值不能推出 的區間極值。

支援區間加值

支援區間加值的區間和查詢

給定一個長度為 的序列 和 筆操作，有兩種操作：

  • 1 x y v：將 之間的元素加上 。
  • 2 x y：詢問 之間的和。

區間加值可以搭配差分技巧實現，令 為差分數列：

區間和就變成：

如此一來，只要維護 和 ，就能實現區間修改的功能。

逆序數對

給定一個長度為 的序列 ，求有幾組數對 滿足 且 。

對於每個位置 ，計算出有幾個 滿足 且 ，逆序數對維護每一個數字各出現幾次，從左到右拜訪，每次找出目前有幾個數字 (全部的個數 - 的個數)，再把 出現個數 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define lowbit(x) ((x) & (-x))
void update(int x)
{
    while (x < MXN)
    {
        ++BIT[x];
        x += lowbit(x);
    }
}

int query(int x)
{
    int ans = 0;
    while (x)
    {
        ans += BIT[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    while (cin >> n)
    {
        int ans = 0, x;
        memset(BIT, 0, sizeof(BIT));
        for(int i = 1; i <= n; ++i)
        {
            cin >> x;
            ++x;
            update(x);
            ans += i - query(x);
        }
    }
}

  1. 樹狀數組 - WiwiHo 的競程筆記 ↩

  2. 前缀和 & 差分 - OI Wiki ↩

  • 最近更新:
  • 本文貢獻者: allem40306,