<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

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`得到

所以可以寫一個函式：

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`

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()

----

## 實作單點加值



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值

<center>
<img src="https://hackmd.io/_uploads/BytojuSt6.png" width="500px">
</center>

----

## 範例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](https://vjudge.net/contest/694552)