# 區間問題概述
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](/@wiwiho/BypP_uUcS)

很多題目和「區間」有關，區間指的是序列中一段連續的部分，而很多題目會同時出現修改和查詢兩種操作，例如：

> 給一個長度為 $n$ 的數列，接下來有 $q$ 筆詢問，詢問有兩種類型：
> 1. 將 $[l, r]$ 這個區間的數字全部加上 $x$。
> 2. 輸出 $[l, r]$ 這個區間的最大值。
>
> 輸入第一行有兩個數字 $n$ 和 $q$，接下來有 $q$ 行，每行表示一筆詢問，第一個數字是 $k$，表示詢問的類型：
> - 如果 $k=1$，接下來會有三個數字 $l$、$r$ 和 $x$，表示要將 $[l,r]$ 這個區間中所有數字加上 $x$。
> 如果 $k=2$，接下來會有兩個數字 $l$、$r$，請輸出目前區間 $[l, r]$ 中的最大值。

:::info
一個序列 $A$ 的區間 $[l,r]$ 指的是 $A_l,A_{l+1},...,A_r$。
:::

這是很經典的區間最大值問題，可以看到題目會要求你做兩種事，而且它是一下子要修改、一下子要查詢，如果暴力修改、暴力查詢的話，修改和查詢時間都是 $O(n)$，乘上詢問筆數就會變成 $O(nq)$，看起來還好？

這其實很糟，很多題目 $n,q$ 都 $10^5$ 以上，這個複雜度顯然不夠。接下來介紹的東西都會是用來處理這種關於區間詢問的問題。

## 區間問題的類型

區間問題會有很多種，區間問題的操作（詢問）大致上就分為**修改**和**查詢**兩種。

修改可能是改數字、把數字加上某個值、把數字開根號……等等，也可能一題裡面有多種修改，修改也可能會很複雜，像是把區間裡的第偶數項 $+k$、奇數項 $-k$ 之類的。

查詢也很多種，像是數字的和、最大的數字……等等。

修改或查詢的範圍也有可能不是一個區間，而是單一個位置，這樣稱為**單點修改**和**單點查詢**，否則，就稱為**區間修改**和**區間查詢**。既然是「區間」問題，那查詢和修改中其中一個當然要是區間的，而另一個可以是區間也可以是單點，不同範圍類型的問題，可以套不同的作法，例如：
- 區間修改、區間查詢：線段樹 + 懶人標記
- 區間修改、單點查詢：BIT + 差分
- 單點修改、區間查詢：線段樹／BIT
- 區間修改、沒有查詢：差分
- 區間查詢、沒有修改：前綴和／稀疏表

當然根據題目不同，可以選擇不一樣的作法，哪個類型要用什麼作法也沒有固定，且除了範圍差異之外，不同題目也有查詢的東西、修改的方式的差異，都會影響解法。

## 常用手法

### 前綴和

前綴和是常用來處理區間問題的一個手法，也就是求出數列的每一個前綴所有數字的和。

長度 $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)$，顯然太慢了。

令 $D_i=A_i-A_{i-1}$、$A_0=0$，也就是 $D_i$ 是 $A_i$ 與它前一項的差，如果要把 $[l,r]$ 都加上 $x$，那麼 $A_l - A_{l-1}$ 應該會多 $x$，而 $A_{r+1}-A_r$ 會少 $x$，所以只要把 $D_l$ 加上 $x$、$D_{r+1}$ 減去 $x$ 就好（當然如果 $r+1>n$ 就不用理它），這樣區間修改就變成單點修改了。

至於要怎麼推回 $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$，這樣太久了，之後會介紹到一個叫樹狀數組（BIT）的資料結構來解決這個問題。

$D$ 稱為 $A$ 的差分序列，這是常用於區間問題的手法之一。

### 離散化

有的時候，需要計算一些數字出現了幾次，例如：
$$1,1,2,3,5,3,3,4,4,2,2,2,1$$

在這裡面，$1$ 出現了 $3$ 次、$2$ 出現 $4$ 次……，如果開一個 map 來存每個數字出現了幾次，這樣不方便做區間問題（例如大小介於 $[l,r]$ 的數字出現了幾次），但如果用 vector、陣列之類的來存，也有可能出現很大數字，導致記憶體開不下。

此時就需要用到離散化，把數列中第一小的數字換成 $1$，第二小換成 $2$……依此類推，如果你想要的話，也可以第一大的換成 $1$。如果需要用到原始值做運算，就把原始值和新值的對照表存下來就好。

### 總結

前綴和和差分兩者都可以在 $O(n)$ 的預處理後，$O(1)$ 做到區間操作。差分可以做到 $O(1)$ 區間修改，前綴和可以做到 $O(1)$ 區間和查詢，不過差分不能同時做查詢、前綴和不能同時做修改，而且前綴和只能算和，無法算最大、最小值，所以除了它們之外，還需要更高級的東西來幫助區間操作。