# 前言
這一章講的東西不是單一演算法，而是一組把暴力解優化成可通過解的共同技巧：前綴和、雙指針、滑動視窗、二分搜。它們的共同精神都是：利用資料的某種性質（單調性、可累加性），省略不必要的重複計算。
這章我把 AP325 講義裡分散在各章節的技巧集中起來，並參考 2023 CISCON《Searching》課程（高睿）的架構重新整理。
# 建表（預處理，preprocessing）
最基本也最容易被忽略的技巧：預先處理好一個表，當要用到某個資訊時直接拿表裡算過的資訊，避免重複計算。跟 DP 的精神很像，都有不重複計算相同問題的概念。
# 範例：骰子湊分數
題目來源：CISCON 2023 Searching（Ten Point Round #11 C. Gunjyo 與骰子）
有三顆 100 面骰，每顆骰子的點數都是 1~100，當同時骰了三顆骰子時，點數分別為 a,b,c，那得到的分數可以是 a+b+c 、 a+b×c 、 a×b+c 、 a×b×c 。給 Q 筆詢問，每筆詢問給一個 x，問有幾種方式湊出 x 分。
限制：1≤Q≤2×105，1≤x≤106
若每次詢問都重算一次結果，複雜度為 O(Q×100^3) ，很明顯會 TLE。但若我們預先將每個 x 的答案都記錄起來，複雜度會變為 O(100^3 + Q) 。
做法：開一個陣列紀錄答案，用三層迴圈枚舉 a、b、c 的點數，每次枚舉出 a,b,c 時，將陣列中 a,b,c 能變成的四種分數都加一。最後陣列中的每個 index[x] 儲存的，就會是 x 能用幾種方式湊出來。接下來每筆詢問，就可以用 O(1) 的方式得到答案。
// [來源：CISCON 2023] | |
void solve(){ | |
for(int a=1;a<=MAX_N;a++){ | |
for(int b=1;b<=MAX_N;b++){ | |
for(int c=1;c<=MAX_N;c++){ | |
an[a+b+c]++; | |
an[a+b*c]++; | |
an[a*b+c]++; | |
an[a*b*c]++; | |
} | |
} | |
} | |
int Q; | |
cin >> Q; | |
while(Q--){ | |
int x; | |
cin >> x; | |
cout << an[x] << "\n"; | |
} | |
} |
如果碰到感覺類似的題目，可能組成的答案數量不多（如 2×10^5 內），但答案可能的數字很大時，可以不用陣列，改用 map 來儲存答案。雖然這樣每個詢問的複雜度都會多一個 log，但在很多情況下還是比每次詢問再算答案還要來的好。
# 前綴和（Prefix Sum）
前綴和是最常見的建表技巧，用於快速計算陣列中前綴元素總和的算法。它可以在 O(1) 的時間複雜度內回答關於陣列中任意區間和的問題。
具體來說，如果我們有一個長度為 n 的陣列 a[] ，則前綴和 p[i] 表示從 a[0] 到 a[i] 的元素之和，即：
p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
...
p[i] = a[0] + a[1] + ... + a[i]
可以看出， p[i] 可以通過 p[i-1] 和 a[i] 計算出來： p[i] = p[i-1] + a[i] 。
使用前綴和，我們可以在 O(1) 的時間內回答如下問題：
- 給定區間 [l, r]，求
a[l]+a[l+1]+...+a[r]的值：只要p[r] - p[l-1] - 給定區間 [l, r]，求
a[l]*1+a[l+1]*2+...+a[r]*(r-l+1)的值（力矩型），可以搭配「前綴和的前綴和」
int psum[N]; | |
psum[0] = a[0]; | |
for (int i = 1; i < n; i++) | |
psum[i] = psum[i-1] + a[i]; | |
// 查詢 [l, r] 的區間和（l > 0） | |
int rangeSum = psum[r] - psum[l-1]; |
前綴和算法常用於解決涉及區間和的問題，比如最大子陣列問題和子矩陣求和問題。這一章開頭「支點切割」那題（見 1-2 遞迴）就是用左右兩個方向的前綴和快速算出力矩總和。
二維前綴和同理，用來 O(1) 查詢子矩陣和：
// [來源：本文補充，待替換] | |
//psum [i][j] = 從 (0,0) 到 (i,j) 這個矩形的總和 | |
for (int i = 1; i <= n; i++) | |
for (int j = 1; j <= m; j++) | |
psum[i][j] = a[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]; | |
// 查詢子矩陣 [x1,y1] 到 [x2,y2] 的和 | |
int sum = psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]; |
# 雙指針（Two Pointers）
跟枚舉有點像，利用一些性質，來省略不必要的枚舉，實作上真的就是兩個指針在跑。
# 範例：兩個遞增序列的和
有兩個長度為 n 且遞增的序列 A, B，你可以從中各選擇一個數，問有幾種選法會使選擇的兩個數的和大於 m。
限制：1≤n≤2×10^5
暴力解是雙層迴圈枚舉 A、B 各一個數， O(n^2) 。但注意到 A、B 都是遞增的，這件事就給了我們單調性：如果 A[i] + B[j] > m ，那麼 A[i] + B[j+1], A[i] + B[j+2], ... 一定也都大於 m（因為 B 遞增）。
利用這個性質，可以讓一個指針固定往一個方向移動，另一個指針跟著調整，兩個指針總移動次數不超過 2n ，所以整體是 O(n) 。
// [來源：本文補充，待替換] | |
// A, B 已由小到大排序 | |
long long cnt = 0; | |
int j = n - 1; | |
for (int i = 0; i < n; i++){ | |
while (j >= 0 && A[i] + B[j] > m) j--; | |
// 此時 B [j+1..n-1] 都能與 A [i] 湊出超過 m 的和 | |
cnt += n - 1 - j; | |
} |
# 範例：CSES 1640 Sum of Two Values
有個長度為 n 的序列 a 和數字 m，求兩個不同的位置 i,j 滿足 a[i]+a[j]=m 。
限制：1≤n≤2×10^5
排序後用左右兩個指針從兩端往中間夾：如果當前和太小，左指針右移；太大，右指針左移；相等就找到答案。因為排序後具有單調性，這樣可以保證不漏掉任何解，複雜度 O(n log n) （含排序）。
// [來源：本文補充，待替換] | |
sort(a.begin(), a.end()); | |
int l = 0, r = n - 1; | |
while (l < r){ | |
long long sum = a[l] + a[r]; | |
if (sum == m) { /* 找到答案 */ break; } | |
else if (sum < m) l++; | |
else r--; | |
} |
# 範例：CSES 1641 Sum of Three Values
同樣的序列，求三個不同位置 i,j,k 滿足 a[i]+a[j]+a[k]=m 。
限制：1≤n≤5000
這是雙指針很典型的升維應用：外層固定一個數 a[i] ，內層對剩下的部分做「Sum of Two Values」。外層 O(n) ，內層 O(n) ，整體 O(n^2) ，在 n≤5000 的限制下完全可以接受。
// [來源：本文補充，待替換] | |
sort(a.begin(), a.end()); | |
for (int i = 0; i < n; i++){ | |
int l = i + 1, r = n - 1; | |
long long target = m - a[i]; | |
while (l < r){ | |
long long sum = a[l] + a[r]; | |
if (sum == target) { /* 找到答案 (i,l,r) */ break; } | |
else if (sum < target) l++; | |
else r--; | |
} | |
} |
這個「固定一維，剩下用雙指針」的模式非常常見，之後遇到 k-sum 系列的題目都可以照這個套路往上疊。
# 滑動視窗（Sliding Window）
滑動視窗其實也是雙指針的一種，因為實際過程像是一個視窗不斷的平移，而得到這個名稱。跟一般雙指針的差別是：滑動視窗維護的是一個連續區間，並且這個區間會隨著左右指針同時往右移動。
# 範例：固定和上限的區間數
給一個長度為 n 的序列 a 和數字 s，問 a 中有幾個區間滿足區間內元素的和不大於 s。
限制：1≤n≤2×10^5，1≤a 的任意元素≤109，1≤s≤1018
因為題目的元素都是正數，區間和具有單調性：右界固定時，左界越往右，區間和越小；左界固定時，右界越往右，區間和越大。這正是滑動視窗能用的條件。
作法：維護一個視窗 [l, r]，r 一路往右擴張；每次擴張後，只要視窗內的和超過 s，就把 l 往右縮，直到和不超過 s 為止。因為 l 跟 r 都只會往同一個方向移動，兩者總移動次數合計是 O(n) ，所以整體複雜度是 O(n) 。
// [來源：本文補充，待替換] | |
long long sum = 0, ans = 0; | |
int l = 0; | |
for (int r = 0; r < n; r++){ | |
sum += a[r]; | |
while (sum > s){ | |
sum -= a[l]; | |
l++; | |
} | |
ans += r - l + 1; // 以 r 結尾、和不超過 s 的區間數 | |
} |
# 範例：leetcode 76. Minimum Window Substring
給兩個字串 s, t，問 s 中最小的區間，滿足 t 的每個字元在該區間中皆能對應到一個與自己相同的字元（t 中重複出現的字元不可對應到選中區間中相同的字元），並輸出這個區間的所有字元。
限制：1 ≤ s.size (), t.size () ≤ 2×10^5，s 與 t 的所有字元皆為英文字母
這是滑動視窗處理字元計數問題的經典模板：用一個 map 或陣列紀錄「還缺多少種字元」，右指針擴張視窗直到涵蓋了 t 的所有字元，接著左指針盡量縮小視窗（同時維持涵蓋條件），紀錄過程中最短的合法區間。因為左右指針都只往右移動，複雜度是 O(|s| + |t|) 。
這題我在這裡只點出思路，實作留給讀者練習 —— 這正是滑動視窗最典型的應用場景：「找滿足某個條件的最短／最長連續區間」。
# 判斷能不能用滑動視窗的關鍵
滑動視窗（以及雙指針）能用的前提是單調性：當視窗擴大，某個要檢查的量只會往一個方向變化（例如和只會變大、種類數只會變多）。沒有這個性質，指針就無法保證不漏解、不重複，這時候還是得回到暴力枚舉，或考慮其他資料結構。
# 二分搜（Binary Search）
# 核心概念
每個人的二分搜都有自己的寫法，平時只要用自己最熟悉的方式就好了。核心概念在於「二分」：如果把問題一般化，想像有一個由 0/1 組成的序列，任意 0 都在任意 1 的左邊（如 00011 ），用二分搜的方式找出從左往右第一個出現的 1 是在哪個位置。
這正是 1-1 提到的自寫二分搜的核心思路：把「是否滿足條件」看成一串 0/1，二分搜就是在找 0 跟 1 的分界點。
# 二分搜的常見 bug
雖然二分搜本身的概念不難，但細節和寫法都很多，還容易出 bug。常見的錯誤：
- 沒有單調性：忘記排序、或題目本來就不符合二分搜的前提
- 初始左右界設錯：導致
L~R太小，答案不再搜尋範圍中；或 L 太小、R 太大，得到 mid 後卻在計算過程 overflow -
L+R時 overflow：兩個很大的數相加可能超過 int 範圍 - 負數運算：
/對負數是無條件捨去絕對值（趨向 0），跟數學上的「向下取整」不同，容易造成 mid 算錯
解決方法：
- 思考極端狀況下 L 跟 R 的範圍，若是怕範圍太大計算數值時 overflow，則 L 跟 R 可以用數學公式算，或者就在計算前先特判會不會 overflow
- 針對第 3、4 點：將寫法從
(L+R)/2改為L+(R-L)/2
為什麼 L+(R-L)/2 可以解決負數運算的問題？因為 R-L 一定是正數（假設 L ≤ R），所以 (R-L)/2 一定是正確的向下取整，不會受到 C++ 對負數除法「趨向 0 捨去」的特性影響。同時 R-L 通常比 L+R 小很多，也降低了 overflow 的風險。
# 該想清楚的三個細節
寫二分搜之前，先想清楚這三件事，可以避免大部分的 bug：
- 當前區間大小為 2 時，mid 會指向左邊還右邊的元素？（取決於
(l+r)/2是向下取整） - 當 L 跟 R 移動時，它們跟 mid 的關係是什麼？（L 會不會設成 mid，還是 mid+1？R 同理）
- 當跳出迴圈時，答案的位置跟 L 或 R 的關係是什麼？
這三點沒想清楚就照抄模板，很容易出現差一個的錯誤（off-by-one）。我自己習慣用左閉右開區間（見 1-1 的 binary_search 寫法），因為終止條件跟區間定義都很明確，不容易搞混。
# C++ 內建的二分搜工具
binary_search(it_L, it_R, val)：回傳一個 bool，代表在[it_L, it_R)中是否有找到 vallower_bound(it_L, it_R, val)：回傳一個 iterator，指向[it_L, it_R)中第一個不小於 val 的位置upper_bound(it_L, it_R, val)：回傳一個 iterator，指向[it_L, it_R)中第一個大於 val 的位置
// [來源：CISCON 2023] | |
vector<int> a={0,1,3,6,10}; | |
cout << binary_search(a.begin(),a.end(),3) << "\n"; | |
auto it1=lower_bound(a.begin(),a.end(),3); | |
cout << "pos=" << it1-a.begin() << " val=" << *it1 << "\n"; | |
auto it2=upper_bound(a.begin(),a.end(),3); | |
cout << "pos=" << it2-a.begin() << " val=" << *it2 << "\n"; |
輸出：
1
pos=2 val=3
pos=3 val=6
使用內建工具的好處：比自己寫快，而且只要使用方式正確就能避免出錯（前提是資料真的排序好了）。
注意：這些函式使用的前提是資料已經由小到大排序。如果需要由大到小或其他自訂順序，要嘛自己實作二分搜（見 1-1），要嘛傳入自訂的比較函式。
# 對答案二分搜
對答案二分搜，顧名思義就是對答案二分搜。使用時機：發現答案符合 0/1 序列的性質，且不會 TLE 時。
這是二分搜最強大的應用，也是很多「看起來不像二分搜」的題目的真正解法。核心想法是：與其直接求答案，不如把問題轉換成「答案是不是至少 x？」這個 yes/no 問題，如果這個判斷式（通常叫 check(x) ）具有單調性（x 越大越容易滿足，或越小越容易滿足），就可以對 x 二分搜。
# 範例：CSES 1620 Factory Machines
有 n 台機器，第 i 台機器可以用 k[i] 的時間製造一個產品，問製造 t 個產品最少需要多久。
限制：1≤n≤2×105，1≤t≤109，1≤k[i]≤10^9
直接求「最少需要多久」不好想，但反過來問「給定時間 x，是否能在 x 時間內做出至少 t 個產品？」就很好判斷 —— 只要把每台機器在 x 時間內能做的量 x/k[i] 加總，看是否 ≥ t 即可，這是 O(n) 。
而這個判斷式滿足單調性：時間 x 越長，能做出的產品數量只會越多（不會變少）。所以可以對「時間」這個答案做二分搜，每次呼叫一次 check(x) 判斷，外層二分搜是 O(log(範圍)) ，整體複雜度 O(n log(範圍)) 。
// [來源：本文補充，待替換] | |
bool check(long long x, vector<long long>& k, long long t){ | |
long long produced = 0; | |
for (long long ki : k){ | |
produced += x / ki; | |
if (produced >= t) return true; // 提早結束，避免 overflow | |
} | |
return produced >= t; | |
} | |
long long l = 1, r = (long long)2e18; | |
while (l < r){ | |
long long mid = l + (r - l) / 2; | |
if (check(mid, k, t)) r = mid; | |
else l = mid + 1; | |
} | |
//l 即為答案 |
# 判斷能不能用對答案二分搜
拿到一題如果直接求答案很難，但「答案是否至少（或至多）為 x」這件事容易判斷，而且隨著 x 增加，判斷結果具有單調性（一旦從否變成是，就不會再變回否），就可以考慮對答案二分搜。這在最大化最小值 / 最小化最大值類型的題目中特別常見（後面圖論章節的「蓋步道」就是這個套路）。
# 對浮點數二分搜
跟對答案二分搜的精神一樣，只是答案本身是浮點數。使用時機同樣是：發現答案可以二分搜（符合 0/1 序列的性質），且不會 TLE 時。
主要差別在於不能用「相等」判斷終止，因為浮點數幾乎不可能精確相等。做法是固定跑一個足夠的迴圈次數（例如 100 次，每次區間減半，100 次後精度遠超過一般題目要求的誤差範圍），或是用「區間長度小於 eps」當終止條件：
// [來源：本文補充，待替換] | |
double l = 0, r = 1e7; | |
for (int iter = 0; iter < 100; iter++){ | |
double mid = (l + r) / 2; | |
if (check(mid)) r = mid; | |
else l = mid; | |
} | |
//l（或 r）即為答案，誤差極小 |
固定跑 100 次是比較保險的寫法，因為浮點數二分搜的迴圈次數不好用「區間變 0」判斷（浮點數精度有限，區間可能永遠縮不到 0，導致無窮迴圈）。
# 小結
| 技巧 | 前提條件 | 複雜度優化 |
|---|---|---|
| 前綴和 / 建表 | 查詢在建表之後、可重複利用 | 每次查詢從 O(n) 降到 O(1) |
| 雙指針 | 資料具單調性（通常需先排序） | 從 O(n^2) 降到 O(n) |
| 滑動視窗 | 連續區間 + 單調性 | 從 O(n^2) 降到 O(n) |
| 二分搜 | 資料已排序 | 從 O(n) 降到 O(log n) |
| 對答案二分搜 | 判斷式 check(x) 具單調性 |
把「求值」轉成「求界」， O(log(範圍)) 次判斷 |
這些技巧的共同心法是：先看資料或答案有沒有單調性，有的話幾乎都能把複雜度降一個檔次。之後遇到題目 TLE，第一件事就是回頭檢查有沒有漏看的單調性。
下一章要講窮舉暴搜與回溯法 —— 當真的找不到單調性或更好的結構時，就得靠有技巧的暴力來解決問題，重點會放在剪枝跟折半枚舉。
# 練習題
（之後補上）
