離散化+BIT

Introduction to Competitive Programming
2/27

• Binary Indexed Tree(BIT)
• 離散化

Binary Indexed Tree(BIT)

中文稱「樹狀數組」

先看題目：

長度為 \(N\) 的序列，\(Q\)筆操作，每次為以下兩種

• 詢問整個序列某前綴總和([\(1..p\)]總和)
• 某個位置的值+=v

\(1\le N,Q\le 10^5\)

暴力的做法？(\(1\le N,Q\le 10^5\))

\(O(N)\)query, \(O(1)\)update   \(O(NQ)\) \(\to\) TLE

BIT能做什麼事？

1. 單點加值 \(O(\log N)\)
2. 動態求前綴總和 \(O(\log N)\)

Binary Indexed Tree \(\to O(logN)\)query \(O(logN)\)update

BIT原理

要求出前綴[1..7]的總和

\(a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7\)

BIT會分解成\(a_{[1..4]}\) \(+\) \(a_{[5..6]}\) \(+\) \(a_{[7..7]}\)

利用二進制分解，只需要查詢最多\(logN\)個區間

BIT結構

BIT[16]=區間[1,16]的總和
BIT[12]=區間[9,12]的總和
BIT[6]=區間[5,6]的總和

BIT初始化

總共有\(n\)個區間，每個區間用一個位置紀錄總和，開長度為\(n\)的vector

void init(int _n){
    n=_n+1;
    vector<int>BIT(n,0);
}

BIT查詢

查詢前綴[1,7]：BIT[7]+BIT[6]+BIT[4]
查詢前綴[1,13]：BIT[13]+BIT[12]+BIT[8]

觀察位元

• 查詢前綴[1..7]=BIT[7]+BIT[6]+BIT[4]：
  7 \(\to\) 6 \(\to\) 4
  00111 \(\to\) 00110 \(\to\) 00100

• 查詢前綴[1..13]=BIT[13]+BIT[12]+BIT[8]：
  13 \(\to\) 12 \(\to\) 8
  01101 \(\to\) 01100 \(\to\) 01000

規律：去除掉最後一個位元1！

\(lowbit(x)\)

用來求出當前\(x_{(2)}\)最右邊位元為1的值

\(20_{(10)}\) \(\to\) 10100\(_{(2)}\) \(\to lowbit(20)=\) 00100\(_{2}\) \(\to\) \(4_{(10)}\)

\(27_{(10)}\) \(\to\) 11011\(_{(2)}\) \(\to lowbit(27)=\) 00001\(_{2}\) \(\to\) \(1_{(10)}\)

\(lowbit(x)\)

根據位元運算知識

lowbit(x)可以由x&-x得到

所以可以寫一個函式：

int lowbit(x){
    return (x&-x);
}

注意0沒有lowbit

實作查詢

• 查詢前綴[1..7]：
  7 \(\to\) 6 \(\to\) 4       00111 \(\to\) 00110 \(\to\) 00100

• 查詢前綴[1..13]：
  13 \(\to\) 12 \(\to\) 8   01101 \(\to\) 01100 \(\to\) 01000

int query(int x){
    int ret=0;
    for(;x>0;x-=lowbit(x)){
        ret+=BIT[x];
    }
    return ret;
}

最多求logn個位置的總和，用\(O(logn)\)的複雜度取得前綴 ✅

回到題目：

長度為 \(N\) 的序列，\(Q\)筆操作，每次為以下一種

• 詢問整個序列某前綴總和([\(1..p\)]總和)✅
• 某個位置的值+=v?

\(1\le N,Q\le 10^5\)

單點更新

位置3加上v \(\to\) BIT[3],BIT[4],BIT[8],BIT[16]這些區間加上v
位置11加上v \(\to\) BIT[11],BIT[12],BIT[16]這些區間加上v

一樣觀察位元

• 位置3加上v \(\to\) BIT[3],BIT[4],BIT[8],BIT[16]這些區間加上v
  

• 位置11加上v \(\to\) BIT[11],BIT[12],BIT[16]這些區間加上v
  

每一步都是加上自身的lowbit()

實作單點加值

void update(int x,int v){
    for(;x<n;x+=lowbit(x)){
        BIT[x]+=v;
    }
}

最多對logn個位置加值，複雜度：\(O(logn)\)✅

BIT模板

struct Binary_Indexed_Tree{
    int n;
    vector<long long> bit;
    int lowbit(x){
        return x&-x;
    }
    void init(int _n){
        n = _n+1;
        bit = vector<long long>(n,0);
    }
    void update(int x,int v){
        for(; x<n; x+=lowbit(x)){
            bit[x] += v;
        }
    }
    long long query(int x){
        long long ret = 0;
        for(; x>0; x-=lowbit(x)){
            ret += bit[x];
        }
        return ret;
    }
}BIT;

BIT 變化

上面的部分為「單點加值」、「區間查詢」

也可以反著做「區間加值」、「單點查詢」

BIT區間\([l,r]\)加值、單點\(x\)查詢

根據前面所說的，可以知道在BIT裡做單點p加值
[1..p],[1..p+1],[1..p+2]…,[1..n]這些前綴和都會加值

BIT區間\([l,r]\)加值、單點\(x\)查詢

這時候要做區間\([l,r]\)加值\(v\)
可以在單點\(l\)加值，在單點\(r+1\)減值：
[1..l],[1..l+1],[1..l+2]…,[1..r]這些前綴和都會加值

BIT.update(l,v);
BIT.update(r+1,-v);

BIT區間\([l,r]\)加值、單點\(x\)查詢

在BIT裡query單點x的前綴和就是x的值：

BIT.query(x);

BIT區間\([l,r]\)加值、單點\(x\)查詢

這個技巧叫做差分，有很多題目都會用到這個技巧。

void range_update(int l,int r,int v){
    BIT.update(l,v);
    BIT.update(r+1,-v);
}
int query(int x){
    BIT.query(x);
}

總結

• 空間：N
• 複雜度：\(O(\log N)\)
• 常數：小(迴圈)
• code長度：短
• 功能：只支援有「结合律 且 有逆運算」的操作(+ &-, xor)
• 注意用BIT要1-base，0不具有lowbit
  像是區間求最大值、最小值之類的題目BIT可能幫不上忙:(

休息一下，等等有例題講解

逆序數對

給定一個長度為 \(n\) \((1 \le n \le 2 \cdot 10^5)\) 的序列 \(a\)\((-10^9 \le a_i \le 10^9)\)，
求有數列中有多少組逆序數對?

如果一組 \((i, j)\) 是逆序數對，則滿足以下公式

\(1 \le i < j \le n，a[i] > a[j]\)

a = [4, 1, 3, 2, 5] 有四組逆序數對

則其中 (4,1), (4,3), (4,2), (3,2) 為逆序數對

想法

BIT的每個位置x可以存x這個數字出現了幾次
利用BIT求前綴和的特性算答案

既然BIT存的是數字出現次數
呼叫BIT.query(x-1)
就可以知道BIT內有幾個數字小於x

a = [4, 1, 3, 2, 5]

對於位置\(i\)，我要找有幾個a[\(i\)]>a[\(j\)]\((i<j)\)

a[0]後面有3個數字小於a[0]
a[1]後面有0個數字小於a[1]
a[2]後面有1個數字小於a[2]
a[3]後面有0個數字小於a[3]
a[4]後面有0個數字小於a[4]

答案為3+0+1+0+0=4

作法

一開始開一個全空的BIT

• 從序列後面開始做到前面
• 每次先query(a[i]-1)
• 再把a[i]加進整個BIT

每次query相加即為答案

細節

由於\((-10^9 \le a_i \le 10^9)\)，所以砸BIT前要先進行離散化

離散化的用處

像這題的數字範圍很大，經過離散化後可以把這\(n\)個\(a_i\)們都壓成\((1 \le a_i \le n)\)的值域範圍。
因為值域範圍縮小，在有些題目上就會比較好做

怎麼離散化

把\(arr[n]=[5,60,6,11,6,60,80]\)離散化：

• 複製一份\(arr\)陣列到另一個陣列\(tmp\)
• 以小到大排序\(tmp\)陣列
• 使用std::unique把\(tmp\)重複的數字去掉
• 利用std::lower_bound將\(arr[i]\)設為在\(tmp_{[0..len-1]}\)查到的index值

範例code

// arr[i] 是初始陣列,長度為n,且0-base
for(int i = 0; i < n; i++)//將arr複製到tmp
    tmp[i] = arr[i];
sort(tmp, tmp + n);//排序
int len = unique(tmp, tmp + n) - (tmp);//把tmp裡重複的數字去掉
for (int i = 0; i < n; i++)
  arr[i] = lower_bound(tmp, tmp + len, arr[i]) - tmp;//二分搜

範例code(用vector)

//vector<int> arr;
vector<int> tmp(arr);  //將arr複製到tmp
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; i++)
  arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

逆序數對的複雜度

先離散化，再每個位置進行一次query和update

離散化複雜度 \(O(nlogn)\)
n次BIT.query複雜度 \(O(nlogn)\)
n次BIT.update複雜度 \(O(nlogn)\)
總複雜度：\(O(nlogn)\)

二維偏序問題

給定一個長度為 \(n\) \((1 \le n \le 2 \cdot 10^5)\) 的序列 \(a\)和 \(b\)\((-10^9 \le a_i,b_i \le 10^9)\)
有幾對\((i,j)\)滿足\(a[i]<a[j]\)且\(b[i]<b[j]\)

二維偏序問題

假設a=[4,3,5]，b=[1,2,3]
那\((i,j)\)可以為\((1,3),(2,3)\)

想法

很像上一題的逆序數對只是多了一組數字
如果少了一組數字的限制的話就可以用同樣的方法做了！

我們先把a,b綁在一起
假設a=[4,3,5],b=[1,2,3]
得到多對\((a,b)=(4,1),(3,2),(5,3)\)

對a排序\(\to\) \((3,2),(4,1),(5,3)\)
這時候a的部分一定滿足\(a[i]<a[j]\)
a=[3,4,5]
b=[2,1,3]

再對b用跟逆序數對相同的做法就是答案

如果a陣列內有相同的數字？
假設a=[2,1,4,3,3,5]，b=[3,3,4,1,2,3]

對a排序得到 \(\to\) a=[1,2,3,3,4,5]，b=[3,3,1,2,4,3]

如果用上面教的方法，紅色位置部分的步驟會像這樣：

BIT.query(0);
BIT.update(1,1);
BIT.query(1);//在這裡會搜到上一個update的1
BIT.update(2,1);

紅色的部分會互相算到

可以考慮把a相同的部分記起來，分別去做query，再一起做update

a=[1,2,3,3,4,5]，b=[3,3,1,2,4,3]

BIT.query(0);
BIT.query(1);//相同的a統一先query再做update
BIT.update(1,1);
BIT.update(2,1);

這樣就可以避免重複算到的問題了

題單：
homework link