# 進階資料結構與莫隊算法—區間問題概述 ###### 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$……