108 師大附中校隊培訓區間指的是序列中一段連續的部分
有些題目會叫你修改某個區間
或問你某個區間的各種值
（例如最大、最小、數字和、公因數……）
也可能有修改、也有查詢
給一個長度為 \(n\) 的數列
接下來有 \(q\) 筆詢問
詢問有兩種類型：
這是很經典的區間最大值問題
題目會要求你做兩種事
而且它是一下子要修改、一下子要查詢
暴力修改、暴力查詢？
修改和查詢時間都是 \(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\)……