# 進階資料結構與莫隊算法—區間問題概述
###### tags: `108 師大附中校隊培訓`
###### wiwiho

---

## 什麼是區間問題

----

區間指的是序列中一段連續的部分

----

有些題目會叫你修改某個區間
或問你某個區間的各種值
（例如最大、最小、數字和、公因數……）

也可能有修改、也有查詢

----

給一個長度為 $n$ 的數列
接下來有 $q$ 筆詢問
詢問有兩種類型：
1. 將 $[l, r]$ 這個區間的數字全部加上 $x$。
2. 輸出 $[l, r]$ 這個區間的最大值。

----

這是很經典的區間最大值問題

題目會要求你做兩種事
而且它是一下子要修改、一下子要查詢

----

暴力修改、暴力查詢？

修改和查詢時間都是 $O(n)$
乘上詢問筆數就會變成 $O(nq)$

----

有點慢？

這種問題非常多元
有很多手法和資料結構
來處理這種問題

---

## 區間問題的類型

----

## 操作（詢問）類型

### 修改
可能是改數字、把數字加上某個值、把數字開根號……等等
可能一題裡面有多種修改
也可能會很複雜

### 查詢
數字的和、最大的數字……

----

## 範圍類型

區間：可能不只一個數字
單點：只有一個數字

----

- 區間修改、區間查詢
- 區間修改、單點查詢
- 單點修改、區間查詢
- 區間修改，沒有查詢
- 區間查詢，沒有修改

----

不同範圍類型的問題
可以套不同的作法

----

根據題目不同
可以選擇不一樣的作法

---

## 前綴和

----

長度 $n$ 的數列 $A=\{A_1,A_2,...,A_n\}$
令 $S_i=\sum_{k=1}^i A_k$

$S$ 就是 $A$ 的前綴和序列
每一個 $S_i$ 都是 $A$ 的一個前綴和

----

給一個長度為 $n$ 的數列 $A=\{A_1,A_2,...,A_n\}$
有 $q$ 筆詢問
每筆詢問求區間 $[l,r]$ 所有數字的和

----

只有查詢區間和
不過如果暴力做
複雜度會變成 $O(nq)$

----

用前綴和去想

----

$$S_r-S_{l-1}=\sum_{k=0}^r A_k-\sum_{k=0}^{l-1}A_k
\\=\sum_{k=l}^r A_k$$

----

$O(n)$ 把所有前綴和算出來
每次查詢都只要 $O(1)$

→複雜度 $O(n+q)$

---

## 差分序列

給一個長度 $n$ 的數列 $A=\{A_1,A_2,...,A_n\}$
有 $q_1$ 次修改
每次修改將 $[l,r]$ 範圍中所有數字都加上 $x$

接著有 $q_2$ 次查詢
請輸出最後 $A_k$ 為多少

$1 \leq n,q_1,q_2 \leq 10^5$

----

做完全部修改，再做查詢

----

如果在區間修改的時候硬做
複雜度會變成 $O(nq_1)$

----

令 $S_i=A_i-A_{i-1}$、$A_0=0$
也就是 $S_i$ 是 $A_i$ 與它前一項的差

$[l,r]$ 都加上 $x$
那麼 $A_l - A_{l-1}$ 應該會多 $x$
而 $A_{r+1}-A_r$ 會少 $x$

----

區間修改變成單點修改了

----

怎麼推回 $A$？
$$\sum_{i=1}^k S_i=(A_1-A_0)+(A_2-A_1)+...+(A_k-A_{k-1})
\\=A_k$$

----

算出前綴和就可以得到 $A_k$ 了
這麼做一遍的話是 $O(n)$

如果是全部修改完再做查詢
就只要 $O(n)$ 算一次 $A$
再 $O(1)$ 查詢

----

一下修改、一下查詢？

每次修改完都要再重新花 $O(n)$ 算一次 $A$
太久

---

## 離散化

----

計算數字出現了幾次

$$1,1,2,3,5,3,3,4,4,2,2,2,1$$

$1$ 出現了 $3$ 次、$2$ 出現 $4$ 次……

----

如果開一個 map
來存每個數字出現了幾次？

不方便做區間問題
（例如大小介於 $[l,r]$ 的數字出現了幾次）

----

用 vector、陣列？

可能出現很大數字，導致記憶體開不下

----

用離散化

把數列中第一小的數字換成 $1$
第二小換成 $2$……