---
# System prepended metadata

title: 資料結構

---

# 資料結構
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$

![V0ZJKmh](https://hackmd.io/_uploads/S1ULi7JEC.png)

[圖源](https://hackmd.io/@arutoria/Syo94XsuH)

然後，因為$lowbit$的神奇性質，我們發現加上自己的$lowbit$就能往上走一層，重複直到最上層就能走過所有**包含自己的區間**。我們又發現減去自己的$lowbit$就能往左走一格，重複走到底就能**不重複涵蓋1到自己**。更酷的是，兩種操作都是$O(logn)$

![ymPdphz](https://hackmd.io/_uploads/S1_dWNy4R.png)

[圖源](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

線段樹。功能多、原理好懂，基本上功能涵蓋前面兩種資料結構。唯一的缺點就是有點難寫。

### 原理

![螢幕擷取畫面 (42)](https://hackmd.io/_uploads/rkSE9ru4R.png)

以區間最大值為例，首先在根節點儲存全部的最大值，接著不斷分成左右兩半，直到不能再分割就完成了。

#### 單點修改、查詢

如果要修改、查詢一個點，只要從根節點不斷遞迴即可。需要注意的是，修改時要在遞迴結束時由下而上把經過的點都修改。因為樹的高度為$log_2n$，複雜度$O(logn)$

例如要查詢index=3的值
![螢幕擷取畫面 (43)](https://hackmd.io/_uploads/Hk-CnS_E0.png)

#### 區間查詢

如果要一次查詢整個區間，則我們把每個節點分成三種情況
設[wL,wR]是我們要查詢的區間，而[L,R]是目前所在節點的區間

1. 若$R<wL或wR<L$ 不包含 (綠色)
2. 若$wL≤L且R≤wR$ 完全包含 (藍色)
3. 若不是上面兩種 部分包含 (黃色)

![未命2名](https://hackmd.io/_uploads/ByOoe8dEC.png)

接著就能根據分類做出三種操作:

1. 不包含:直接退出
2. 完全包含:紀錄值然後退出
3. 部分包含:繼續往下遞迴

以[wL,wR]=[2,6]為例:

![螢幕擷取畫面 (44)](https://hackmd.io/_uploads/BymPMUuVR.png)

如圖所示，重複上面的操作，可以發現所有藍色區間連起來會剛好等於我們要查詢的區間，複雜度$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]

![螢幕擷取畫面 (44)](https://hackmd.io/_uploads/BymPMUuVR.png)

那麼，我不只要更新黃色及藍色節點，甚至還要更新藍色節點的所有子節點，複雜度又回到$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(通常非常難抓，也有可能是我太菜)出現。



