# 第三章 :基礎資結
## STL 標準資料結構
### pair
一種存資料的方法，跟`struct`很像，優點是有自定義排序，會先依照前項排序再依照後項排序，||可以偷懶||
$e.g.$
```cpp=+
pair<int, int> p1; // p1 = {0 , 0}
pair<int, int> p3 = {4, 8};
cout<<p3.first<<" "<<p3.second; //4 8
pair<pair<int, int>, int> p4 = {{4, 8}, 7};
cout<<p4.first.first<<" "<<p4.first.second<<" "<<p4.second; // 4 8 7
vector<pair<int, int>> v1(100, {1, 2});
cin>>v1[0].first;
vector<pair<int, int>> v2;
v2.push_back({1, 2});
```
### queue && stack (線性容器)
**可以把`queue`想像成一個水管，只能右進左出，只能訪問最前面跟最後面
而`stack`則是像一個桶子，後進先出，只能訪問最上面**
```cpp=
stack<int> s;
s.push(val):將 val 加進 stack 的最上面,O(1)
s.pop():將 stack 最上面的元素刪除,O(1)
s.top():取得 stack 最上面的元素,O(1)
queue<int> q;
q.push(val):將 val 加進 queue 的最後面,O(1)
q.pop():將 queue 最前面的元素刪除,O(1)
q.front():取得 queue 最前面的元素,O(1)
```
### priority_queue
將最重要的元素放在最頂端，只能訪問最前項，預設是將最大當作最重要
$e.g.$
```cpp=+
priority_queue<int> pq
pq.push(val):將 val 加進 pq 裡面,O(log n)
• pq.pop():將 pq 最上面的元素刪除,O(log n)
• pq.top():取得 pq 最上面的元素,O(1)
/***************************************/
pq.push(1);
pq.push(2);
pq.push(2);
while(!pq.empty()) {
cout<<pq.top()<<" ";
pq.top();
}
//2 2 1
```
* **註 : `pq`的時間常數比`set`還要低**
* [進階語法](https://yuihuang.com/cpp-stl-priority-queue/)
### set&&multiset
$set$主要的功能有`排序`與`去重`：
把資料送入$set$時，若$set$內已有該數值就會被刪除，若沒有就會被排序
**即所有相同資料在$set$中只能存在一個**
```cpp=
set<int> s;
int val=1;
s.empty(); //回傳布林值：s是否為空
s.size(); //回傳整數：s的大小
s.begin(); //回傳迭代器：s最前面的位置
s.end(); //回傳迭代器：s最後位置的下一個位置
s.insert(val); //插入數值val到s中 回傳pair<iterator,bool>插入位置和是否成功 O(log n)
s.count(val); //查看s中val數值的數量（set中必為1或0）O(log n)
s.erase(val); //刪除s中的val元素
s.erase(iterator); //刪除iterator迭代器位置的數值 O(1)
s.find(val); //查找val數值的位置 回傳iterator O(logn)
```
$multiset$是允許多個相同數值存在的$set$
使用方法和$set$大致相同
```cpp=
multiset<int> ms;
int val=1;
ms.empty(); //回傳布林值：s是否為空
ms.size(); //回傳整數：s的大小
ms.begin(); //回傳迭代器：s最前面的位置
ms.end(); //回傳迭代器：s最後位置的下一個位置
ms.insert(val); //插入數值val到s中 O(log n)
ms.count(val); //查看s中val數值的數量 O((val在ms中的個數)log n)
ms.erase(val); //刪除s中的所有val元素 回傳整數被刪除的元素數量 O((val在ms中的個數)log n)
ms.erase(iterator); //刪除iterator迭代器位置的數值 回傳iterator刪除元素的下一個位置 O(1)
ms.find(val); //查找val數值的位置 若有多個數值 回傳最前面的那個 O(logn)
```
需要注意的是，如果想要只刪除$multiset$某個元素一次而不是刪掉所有的這個元素，可以像以下的做法。
```cpp=
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(1);
ms.erase(ms.find(1)); //只會刪掉一個
cout<<ms.size(); //2
ms.erase(1);
cout<<ms.size(); //0
```
### map
用於儲存離散化的資料，像是一個陣列，但陣列索引可能是任何資料型態，特別是當需要開一個很大的陣列的時候可以考慮使用它，通常都以`map<int, int>`來做，每次對map上的東西進行操作時間複雜度都是$O(logn)$，$n$是目前在map上有多少開啟了多少個點
```cpp=
//map<key_type,value_type> mp; 這是宣告方式
map<char,int> mp; //預設每一項都是0
mp['A']; //在mp中宣告一個引索為A的數
mp['A']=1;
mp['A']+=5;
cout<<mp['A']; //6
mp.erase(key); //刪除該索引的
mp.find(key); //回傳該索引的位置 找不到則回傳mp.end()
```
練習題
> [set應用](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a155)
> [離散化](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a532)
> [map](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a177)
> [STL](https://cses.fi/problemset/task/1621)
> [pair排序](https://cses.fi/problemset/task/1629/)
## 並查集 Disjoint Set
[例題](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a531)
又稱互斥集或$DSU$，具有下列功能的資料結構。
> 所有元素 $P$ 編號為 $1,2,3,...,n$。
> 1. 對於$P$中的每個元素$t$都恰有一個集合包含該元素。
> 2. 把$A$,$B$兩個元素所在的集合合併到同個集合中。
> 3. 查詢$A$,$B$兩個元素所在的集合是否是同一個集合。
>
由於$STL$並沒有支援所有我們需要自己實作，值得慶幸的是，這個資料結構實作比較輕鬆。
1. 首先，我們需要紀錄每個元素的$Boss$，每個元素的$Boss$一開始都是自己，如果一個元素的$Boss$=該元素，那這個元素我們就定義它是最大的$Boss$。
2. 如果需要判斷兩個元素是否在同一個集合，可以判斷兩個元素的最大的$Boss$是否相同。
3. 如果要合併兩個集合，就把其中一個元素的最大的$Boss$指定為另外一個元素最大的的$Boss$。
範例 :
```cpp=
#include<bits/stdc++.h>
using namespace std;
const MAXN=2e5+5;
vector<int> boss(MAXN, 0);
void build_dsu() {
for(int i=1;i<MAX;i++) boss[i]=i;
}
int find(int now) {
if(boss[now]=now) return now;
return find(boss[now]);
}
bool same(int x, int y) {
return find(x)==find(y);
}
void union(int x, int y) {
int fx=find(x), fy=find(y);
boss[fx]=fy;
}
```
這個程式的每次操作的時間複雜度是$O(n)$，因為可以觀察到查詢跟合併的操作都是依靠$find()$這個函式，而一個元素要找到它最大的$boss$最多需要執行$n$次，因此整體的時間複雜度式$O(Qn)$，$Q$是總共有幾次操作。
因此我們可以針對$find()$函式進行優化，我們可以發現一個元素的$Boss$的$Boss$一直到這個元素的最大的$Boss$之前，所有的$Boss$的最大的$Boss$都是相同的，因此我們可以把$find()$改成下面的程式，看起來差不多，但是每次查詢的時間複雜度根據均攤分析可以優化到$O(logn)$，這個優化我們稱之為路徑壓縮。
* [維基百科](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity)
* [OI Wiki](https://oi-wiki.org/ds/dsu/)
```cpp=
int find(int now) {
if(boss[now]=now) return now;
return boss[now]=find(boss[now]);
}
```
快還要更快，一個很貪心且直覺的想法就是在合併兩個集合的時候，把比較小的集合的最大的$Boss$，設成比較大的集合的最大的$Boss$，一定比把比較大的集合的最大的$Boss$，設成比較小的集合的最大的$Boss$，因為很顯然的，比較大的集合在更新的最大的$Boss$時需要更多時間，因為元素更多，這樣可以把每次操作的時間優化成$O(\alpha(n))$。
> $\alpha(n)$，的中文是反阿克曼函數，增長很慢，比較直觀的是:$\alpha(2^{2^{2^{2^2}}})=4$，$2^{2^{2^{2^2}}}\approx 2\times10^{19728}$
$DSU .final$
```cpp=
#include<bits/stdc++.h>
using namespace std;
const MAXN=2e5+5;
vector<int> boss(MAXN, 0), sz(MAXN, 1); //一開始的集合大小都是1
void build_dsu() {
for(int i=1;i<MAX;i++) boss[i]=i;
}
int find(int now) {
if(boss[now]=now) return now;
return boss[now]=find(boss[now]);
}
bool same(int x, int y) {
return find(x)==find(y);
}
void union(int x, int y) {
int fx=find(x), fy=find(y);
if(sz[fx]<sz[fy]) swap(fx, fy);
sz[fx]+=sz[fy];
boss[fy]=boss[fx];
}
```
練習題
> [DSU](https://atcoder.jp/contests/abc177/tasks/abc177_d)
> [DSU](https://cses.fi/problemset/task/1676/)
## BIT
又稱作樹狀數組或二元索引樹($Binary$ $Indexed$ $Tree$ $=>$ $BIT$ )，可以在$O(logn)$的時間做到單點改值以及前墜查詢，時間常數低，空間也只要$n$，實作也簡單。
BIT上每一個節點表示的值根據它的位置編號而定，$BIT_i$定義為:以$i$為結尾，長度為$lowbit(i)$的區間和，也就是$[i-lowbit(i), i]$的和。
$lowbit(i)$的定義:把$i$轉成二進制後把除了最低位的1以外的1都變成0，例如:
$$lowbit(26)_{10}=lowbit(11010)_{2}=(00010)_{2}=(10)_{2}=(2)_{10}$$
所以$BIT_{26}$表示的就是$[24, 26]$的區間和。
在程式中可以透過`i&-i`來取得$lowbit(i)$，因為`-x`會是`x`的補數+1，所以最低位的1會變成0，但右邊所有的0都會變成1，再+1之後又會進為讓原本最低位的1從0進位成1，右邊全部的1變回0，再透過`&`運算就可以發現`i&-i`=$lowbit(i)$
例如 $i=26$，$i=(11010)_{2}$，$-i=(1...11100101)_{2}+1=(1...11100110)_{2}$，`i&-i`=2
$BIT_0$代表空區間，$BIT_1$代表的是$[1, 1]$，所以序列的索引應該從1開始
可以把BIT畫成以下兩種形式。
* 圖一
* 圖二
* 節點$i$的父節點是$i-lowbit(i)$
* 節點$i$的深度=2進制下$i$是1的位元數
* 節點$i$的右兄弟節點 ( 如果有的話 ) 是$i+lowbit(i)$
### 單點改值
假設在使用$BIT$想要進行修改的動作，需要修改他的所有右兄弟節點，例如想要修改原陣列節點9的資訊，應該修改是$BIT$中包含節點9的區間:$[9, 9],[9, 10],[9, 12]$，你可以發現就是圖二的節點$9, 10, 12$，也就是節點9的右兄弟節點，實作如下。
```cpp=
void modify(int pos, int val) {
//n是BIT大小
for(;pos<=n;pos+=pos&-pos)
bit[pos]+=val;
}
```
可以發現$pos$會不斷增加，因此時間複雜度是$O(logn)$。
### 區間查詢
如果要查以$i$為結尾的前綴和，需要計算節點$i$與他的祖先節點的和，因為以$i$結尾的區間就是節點$i$ ( 可以去看圖一,圖二 ) ，而節點$i$所代表的區間會完全的接在節點$i$的父節點後，因此只要計算節點$i$與他的祖先節點的和，就能算出以$i$為結尾的前綴和，實作如下。
```cpp=
//以最基礎的BIT為例
int search(int pos) {
int ret=0;
for(;pos;pos-=pos&-pos) {
ret+=bit[pos];
}
return ret;
}
```
可以發現父節點的大小會以2的冪次成長，所以時間複雜度是$O(logn)$。
### 蓋BIT
$modify$每個點，時間是$O(nlogn)$。
### 應用
1. 求區間和: 有了前綴和當然可以求區間和，$[x, y]$的和是$[1, y]-[1, x-1],x\le y$，可以在$O(logn)$做好。
2. 區間加值: 先把原陣列做差分，可以$O(logn)$區間修改，$O(logn)$單點查詢。
3. 如果原陣列每一項都是正數，那$BIT$會是遞增的，因此可以對$BIT$做二分搜，這個技巧也被稱為$BIT$上二分，時間複雜度是$O(lognlogn)$，優化後可以$O(logn)$。
4. 高維BIT: 把$BIT$模板化，$X$維的$BIT$的每個節點存一棵$X-1$維的$BIT$。
5. 求逆序數對: 可以對陣列蓋$BIT$，每次插入$v_i$前查詢$BIT$中大於$v_i$的數量。
練習題
Sign in with Wallet
Connect another wallet