<style> .reveal .slides { text-align: left; font-size:35px; } </style> # 離散化+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)$<!-- .element: class="fragment" data-fragment-index="1" -->query,<!-- .element: class="fragment" data-fragment-index="1" --> $O(1)$<!-- .element: class="fragment" data-fragment-index="1" -->update<!-- .element: class="fragment" data-fragment-index="1" --> &emsp;<!-- .element: class="fragment" data-fragment-index="1" --> $O(NQ)$<!-- .element: class="fragment" data-fragment-index="1" --> $\to$<!-- .element: class="fragment" data-fragment-index="1" --> TLE<!-- .element: class="fragment" data-fragment-index="1" --> ---- ## BIT能做什麼事？ 1. 單點加值 $O(\log N)$ 2. 動態求前綴總和 $O(\log N)$ Binary Indexed Tree<!-- .element: class="fragment" data-fragment-index="2" --> $\to O(logN)$<!-- .element: class="fragment" data-fragment-index="2" -->query<!-- .element: class="fragment" data-fragment-index="2" --> $O(logN)$<!-- .element: class="fragment" data-fragment-index="2" -->update<!-- .element: class="fragment" data-fragment-index="2" --> ---- ## BIT原理 要求出前綴[1..7]的總和 $a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7$ BIT會分解成<font color="B85450">$a_{[1..4]}$</font> $+$ <font color="82B366">$a_{[5..6]}$</font> $+$ <font color="6C8EBF">$a_{[7..7]}$</font> 利用二進制分解，只需要查詢最多$logN$個區間 <img src="https://hackmd.io/_uploads/SkYDQn1Ka.png" width="500px" position="absolute" right="10px" top="10px"> ---- ## BIT結構  BIT[16]=區間[1,16]的總和 BIT[12]=區間[9,12]的總和 BIT[6]=區間[5,6]的總和 ---- ## BIT初始化 總共有$n$個區間，每個區間用一個位置紀錄總和，開長度為$n$的vector ```cpp! void init(int _n){ n=_n+1; vector<int>BIT(n,0); } ``` ---- ## BIT查詢  查詢<span style="background-color: lightpink;"><font color="FF0000">前綴[1,7]：BIT[7]+BIT[6]+BIT[4]</font></span> 查詢<span style="background-color: lightblue;"><font color="3333FF">前綴[1,13]：BIT[13]+BIT[12]+BIT[8]</font></span> ---- ## 觀察位元 - 查詢前綴[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` 規律：去除掉最後一個位元<!-- .element: class="fragment" data-fragment-index="1" -->`1`<!-- .element: class="fragment" data-fragment-index="1" -->！<!-- .element: class="fragment" data-fragment-index="1" --> ---- ## $lowbit(x)$ 用來求出當前$x_{(2)}$最右邊位元為`1`的值 $20_{(10)}$ $\to$ 10`100`$_{(2)}$ $\to lowbit(20)=$ 00`100`$_{2}$ $\to$ $4_{(10)}$ $27_{(10)}$ $\to$ 1101`1`$_{(2)}$ $\to lowbit(27)=$ 0000`1`$_{2}$ $\to$ $1_{(10)}$ ---- ## $lowbit(x)$ 根據位元運算知識 lowbit(x)可以由`x&-x`得到 所以可以寫一個函式： ```cpp! int lowbit(x){ return (x&-x); } ``` 注意0沒有lowbit ---- ## 實作查詢 - 查詢前綴[1..7]： 7 $\to$ 6 $\to$ 4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `00111` $\to$ `00110` $\to$ `00100` - 查詢前綴[1..13]： 13 $\to$ 12 $\to$ 8 &nbsp;&nbsp;`01101` $\to$ `01100` $\to$ `01000` ```cpp! 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  <!-- `00011` $\to$ `00100` $\to$ `01000` $\to$ `10000` --> - 位置11加上v $\to$ BIT[11],BIT[12],BIT[16]這些區間加上v  <!-- `01011` $\to$ `01100` $\to$ `10000` --> ---- -  -  每一步都是加上自身的lowbit() ---- ## 實作單點加值   ```cpp! void update(int x,int v){ for(;x<n;x+=lowbit(x)){ BIT[x]+=v; } } ``` 最多對logn個位置加值，複雜度：$O(logn)$✅ ---- ## BIT模板 ```cpp= 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]`這些前綴和都會加值 ```cpp! BIT.update(l,v); BIT.update(r+1,-v); ``` ---- ## BIT區間$[l,r]$加值、單點$x$查詢 在BIT裡query單點x的前綴和就是x的值： ```cpp! BIT.query(x); ``` ---- ## BIT區間$[l,r]$加值、單點$x$查詢 這個技巧叫做差分，有很多題目都會用到這個技巧。 ```cpp! 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值 <center> <img src="https://hackmd.io/_uploads/BytojuSt6.png" width="500px"> </center> ---- ## 範例code ```cpp! // 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`) ```cpp! //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] 如果用上面教的方法，紅色位置部分的步驟會像這樣： ```cpp! 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] ```cpp! BIT.query(0); BIT.query(1);//相同的a統一先query再做update BIT.update(1,1); BIT.update(2,1); ``` 這樣就可以避免重複算到的問題了 --- 題單： [homework link](https://vjudge.net/contest/694552)