# 資料結構
data structure，就是電腦中儲存資料的方式。之前學過的Stack、Queue、Array等等都是資料結構的一種。與之前不同的是，之前學習的資料結構都是C++內建好的，不需要自己實作，而接下來要教的都是沒有內建的。
## 區間最大值
[Range Minimum Queries](https://cses.fi/problemset/task/1647)
給你一個長度n的陣列，然後有q個詢問:[L,R]區間中的最大值為何?
用暴力法解決，複雜度$O(nq)$，有沒有更快的方式?
## Sparse table
### 原理
我們可以把讀入的數字先分塊，再用一塊一塊的區間組出答案。
例如:$a=[1,8]$的最大值，$b=[5,10]$的最大值。那麼$max(a,b)=[1,10]$的最大值
具體來說，我們把每$2^x(0≤x≤log_2n)$個數字分成一塊，如此一來，對於[L,R]，只要用兩個小於$R-L+1的最大2^x$就能組合出整個區間
以n=8為例:
| x=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| -- | -- | -- | -- | -- | -- | -- | -- |-- |
| x=1 | 1-2 | 2-3 | 3-4 | 4-5 | 5-6 | 6-7 | 7-8 |--|
| x=2 | 1-4 | 2-5 | 3-6 | 4-7 | 5-8 |--|--|--|
| x=3 | 1-8 | -- | -- | -- | -- | -- | -- |-- |
$[1,7] -> [1,4]+[4,7]$
$[2,6] -> [2,5]+[3,6]$
$[L,R] -> [L,L+2^x-1]+[R-2^x+1,R]$
這樣儲存資料的方式(資料結構)稱為Sparse table(稀疏表)，能夠以$O(nlogn+q)$解決區間最大值問題
## 實作
```cpp
int n,q;
cin>>n>>q;
vector<int> v(n+1);
vector<vector<int>> st(__lg(n)+1,v);
for(int i=1;i<=n;i++){
cin>>v[i];
st[0][i]=v[i]; //x=0時,每一塊就是v[i]
}
for(int i=1;i<=__lg(n);i++){ //__lg(n)=log2(n)取整數
int len=1<<i; //現在要算的區間長度=2^i
for(int j=1;j<=n;j++){
if(j+len-1>n) break;
st[i][j]=max(st[i-1][j],st[i-1][j+len/2]);
}
}
int L,R;
for(int i=0;i<q;i++){
cin>>L>>R;
int x=__lg(R-L+1);
cout<<max(st[x][L],st[x][R-(1<<x)+1])<<"\n";
}
```
## 單點修改區間和
[Dynamic Range Sum Queries](https://cses.fi/problemset/task/1648)
給你一個長度n的陣列，然後有q個操作，分為兩種:
1:輸出[L,R]區間和
2:把位置k的數字改為u
用暴力法解決，每次問[L,R]都需要跑最多n次，複雜度$O(nq)$。用之前學過的前綴和解決，會發現每次更改1個點就需要重新計算整個前綴和陣列，複雜度還是$O(nq)$，有沒有更快的方式?
## Binary Indexed Tree
### 原理
定義陣列$BIT[i]=原陣列[i-lowbit(i)+1,i]$的和，這時會發現它等同於把原陣列一直分割成左半邊。
其中，$lowbit(i)=i$ & $-i$
[圖源](https://hackmd.io/@arutoria/Syo94XsuH)
然後，因為$lowbit$的神奇性質，我們發現加上自己的$lowbit$就能往上走一層，重複直到最上層就能走過所有**包含自己的區間**。我們又發現減去自己的$lowbit$就能往左走一格，重複走到底就能**不重複涵蓋1到自己**。更酷的是，兩種操作都是$O(logn)$
[圖源](https://hackmd.io/@arutoria/Syo94XsuH)
### 實作
雖然原理很牛逼但實作卻非常簡單。實作上分為三部分
#### 建構
根據題目給的陣列製造BIT
```cpp
int n; //陣列大小
vector<int> arr; //原陣列
vector<int> BIT; //BIT陣列
int lowbit(int i){
return i&(-i);
}
void build(){
for(int i=1;i<=n;i++){
for(int j=i-lowbit(i)+1;j<=i;j++){
BIT[i]+=arr[j];
}
}
}
```
就照著定義用迴圈來製造初始BIT
#### 修改
題目的2號操作，把位置為k的數字改為u。也就是說，我們修改BIT內所有包含位置k的區間。利用剛剛的神奇性質，只要從k一直加$lowbit$就能走過所有包含k的區間
```cpp
void update(int k,int u){
int add=u-arr[k];
arr[k]=u;
for(int i=k;i<=n;i+=lowbit(i)){
BIT[i]+=add;
}
}
```
#### 查詢
題目的1號操作，要求[L,R]的和。因為一直減去自己的$lowbit$就能不重複涵蓋1到自己，所以可以快速求出[1,R]和[1,L-1]，相減就是[L,R]
```cpp
int sum(int L,int R){
L=L-1;
int sum_L=0,sum_R=0;
for(int i=L;i>0;i-=lowbit(i)){
sum_L+=BIT[i];
}
for(int i=R;i>0;i-=lowbit(i)){
sum_R+=BIT[i];
}
return sum_R-sum_L;
}
```
### 延伸:區間修改單點值
如何用BIT解決?
## Segment tree
線段樹。功能多、原理好懂，基本上功能涵蓋前面兩種資料結構。唯一的缺點就是有點難寫。
### 原理
以區間最大值為例，首先在根節點儲存全部的最大值，接著不斷分成左右兩半，直到不能再分割就完成了。
#### 單點修改、查詢
如果要修改、查詢一個點，只要從根節點不斷遞迴即可。需要注意的是，修改時要在遞迴結束時由下而上把經過的點都修改。因為樹的高度為$log_2n$，複雜度$O(logn)$
例如要查詢index=3的值
#### 區間查詢
如果要一次查詢整個區間，則我們把每個節點分成三種情況
設[wL,wR]是我們要查詢的區間，而[L,R]是目前所在節點的區間
1. 若$R<wL或wR<L$ 不包含 (綠色)
2. 若$wL≤L且R≤wR$ 完全包含 (藍色)
3. 若不是上面兩種 部分包含 (黃色)
接著就能根據分類做出三種操作:
1. 不包含:直接退出
2. 完全包含:紀錄值然後退出
3. 部分包含:繼續往下遞迴
以[wL,wR]=[2,6]為例:
如圖所示，重複上面的操作，可以發現所有藍色區間連起來會剛好等於我們要查詢的區間，複雜度$O(logn)$
### 實作
[Dynamic Range Minimum Queries](https://cses.fi/problemset/task/1649
)
大致有指標型和陣列型兩種方法，一樣分為建構、修改和查詢三部分(以單點修改區間最小值為例)
### 指標型
#### 建構
首先建立node結構，包含val(儲存的值)、L,R(儲存的區間)、cl,cr(左右子節點)
```cpp
struct node{
int val,L,R;
node* cl;
node* cr;
};
```
接著是pull函式，也就是更新節點，方便後面實作
```cpp
void pull(node* k){
k->val=min(k->cl->val,k->cr->val);
}
```
從根節點遞迴往下，直到不能再分割(區間長度是1)
```cpp
int n; //陣列大小
vector<int> v; //原陣列
void build(node* k){
if(k->L==k->R){
k->val=v[k->L];
return;
}
int M=(k->L+k->R)/2;
k->cl=new node{0,k->L,M};
k->cr=new node{0,M+1,k->R};
build(k->cl);
build(k->cr);
pull(k);
}
int main()
{
node* root=new node{0,1,n};
build(root);
return 0;
}
```
#### 修改
一樣從根節點遞迴往下，走到底為止。記得遞迴結束前要更新。
```cpp
void upd(node* k,int pos,int x){
if(k->L==k->R){
k->val=x;
return;
}
int M=(k->L+k->R)/2;
if(pos<=M) upd(k->cl,pos,x);
else upd(k->cr,pos,x);
pull(k);
}
```
#### 查詢
區間查詢，把目前所在區間分成三類
```cpp!
int qry(node* k,int wL,int wR){
if(k->R<wL || wR<k->L) return 1e9;
if(wL<=k->L && k->R<=wR) return k->val;
return min(qry(k->cl,wL,wR),qry(k->cr,wL,wR));
}
```
### 陣列型
陣列型是利用巧妙的編號，在陣列中製造出類似指標的效果。令根節點的編號為1，節點k的左子節點的編號為2k，右子節點為2k+1。則可以用一個陣列儲存每個節點所記錄的值，其大小不超過4n
#### 建構
因為tree中只儲存了val，所以L,R要藉由函式傳遞
```cpp
vector<int> v; //原陣列，大小n
vector<int> tree; //線段樹陣列，大小4n
void bulid(int L,int R,int k){
if(L==R) tree[k]=v[L];
int M=(L+R)/2;
bulid(L,M,2*k);
bulid(M+1,R,2*k+1);
tree[k]=min(tree[2*k],tree[2*k+1]); //等同於pull函式
}
```
#### 修改
```cpp
void upd(int L,int R,int pos,int x,int k){
if(L==R){
tree[k]=x;
return;
}
int M=(L+R)/2;
if(pos<=M) upd(L,M,pos,x,2*k);
else upd(M+1,R,pos,x,2*k+1);
tree[k]=min(tree[2*k+1],tree[2*k]);
}
```
#### 查詢
```cpp
int query(int L,int R,int wL,int wR,int k){
if(L>=wL && R<=wR) return tree[k];
if(L>wR || R<wL) return 1e9;
int M=(L+R)/2;
return min(query(L,M,wL,wR,2*k),query(M+1,R,wL,wR,2*k+1));
}
```
### 分析
以上就是基礎的線段樹實作。它可以單改區查(BIT)、也可以不改，只有查(sparse table)。但是在區間修改的時候會遇到其他問題。
### 懶人標記
上面提到區間修改會出現一些問題。舉例來說，如果要更新[2,6]
那麼，我不只要更新黃色及藍色節點，甚至還要更新藍色節點的所有子節點，複雜度又回到$O(n)$。於是就需要**懶人標記**了。與查詢時相同，找到藍色節點時就停止遞迴。但是，我們幫他打上標記，代表**他的子節點都需要修改**。之後，如果有任何操作(修改、查詢)遇到有標記的節點，就順便更新他的值，複雜度又回到$O(logn)$。
### 例題
[Prefix Sum Queries
](https://cses.fi/problemset/task/2166/)
本題有兩種操作:
1.更新位置k的值成u
2.詢問[L,R]區間中最大的前綴和
#### 題解
以線段樹儲存前綴和，則題目可以變成:
1.更新位置k以及k以後的值，也就是更新區間[k,n]
2.詢問[L,R]區間中的最大值
也就是區間修改的線段樹
### 實作
#### 建構
node結構中新增lazy，lazy=x代表這個節點的所有子節點都要加x
```cpp
struct node{
int val,L,R;
int lazy=0; //懶人標記
node* cl;
node* cr;
};
```
push函式，清空懶人標記，再把懶人標記丟給左右子節點，代表下面都還沒更新。因為子節點的懶標可能不為0，所以要用+=
```cpp
void push(node* k){
k->val+=k->lazy;
if(k->cl) k->cl->lazy+=k->lazy;
if(k->cr) k->cr->lazy+=k->lazy;
k->lazy=0;
}
```
pull及build函式不需修改。
#### 修改
add表示要增加的值，其值為u-v[k]
```cpp
void upd(node* k,int wL,int wR,int add){
if(k->R<wL || wR<k->L) return;
if(wL<=k->L && k->R<=wR){
k->lazy+=add;
return;
}
push(k);
upd(k->cl,wL,wR);
upd(k->cr,wL,wR));
pull(k);
}
```
注意要先push再update子節點，確保子節點的值是對的，接著再pull，確保更新的結果是對的。
#### 查詢
記得要把懶標push下去，這樣查到的值才會是更新過的
```cpp
int qry(node* k,int wL,int wR){
push(k);
if(k->R<wL || wR<k->L) return 1e9;
if(wL<=k->L && k->R<=wR) return k->val;
return min(qry(k->cl,wL,wR),qry(k->cr,wL,wR));
}
```
### 分析
使用懶人標記時，要思考節點的狀態。目前節點的標記更新了嗎?上面的節點的標記有推下來嗎?如果有多種標記，每個標記的順序為何?等等，才能避免bug(通常非常難抓，也有可能是我太菜)出現。
Sign in with Wallet
Connect another wallet