區間問題概述

tags: 108 師大附中校隊培訓

108 師大附中校隊培訓簡報

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

給一個長度為

$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]$ 中的最大值。

一個序列

$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)$。如果用前綴和去想，會發現：

$$\begin{gathered} S_r-S_{l-1}=\sum _{k=0}^r{A}_k-\sum _{k=0}^{l-1}{A}_k \\ =\sum _{k=l}^r{A}_k \end{gathered}$$

所以只要

$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\le n,q_1,q_2\le {10}^5$

雖然這個問題是做完全部修改，再做查詢，讓這題沒有像剛剛那題複雜，但是如果在區間修改的時候硬做，複雜度會變成

$O(n{q}_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$ 呢？注意到

$$\begin{gathered} \sum _{i=1}^k{S}_i=(A_1-A_0)+(A_2-A_1)+...+(A_k-A_{k-1}) \\ =A_k \end{gathered}$$

只要算出前綴和就可以得到

$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)$ 區間和查詢，不過差分不能同時做查詢、前綴和不能同時做修改，而且前綴和只能算和，無法算最大、最小值，所以除了它們之外，還需要更高級的東西來幫助區間操作。