實用技巧 (Tricks)

本章節介紹在 APCS 與程式競賽中極為實用的技巧。這些技巧通常能將演算法的時間複雜度從 \(O(N^2)\) 優化至 \(O(N)\) 或 \(O(1)\)，是解決區間查詢與修改問題的利器。

1. 前綴和

#

區間求和的基礎技巧。透過預處理，將原本 \(O(N)\) 的區間查詢優化至 \(O(1)\)，亦包含二維前綴和的應用。

2. 差分

#

針對區間修改的技巧。利用差分陣列紀錄變化量，將原本 \(O(N)\) 的區間加減操作優化至 \(O(1)\)，常與前綴和搭配還原陣列。

3. 單調性

#

介紹函數或數列的單調性質（遞增或遞減），這是二分搜尋法與許多貪心策略成立的基礎觀念。

4. Deque 雙端佇列

#

介紹 deque 資料結構，它允許在佇列的前端與後端進行 \(O(1)\) 的插入與刪除操作，比 vector 更有彈性。

5. 題解：靜態區間求和

#

CSES Static Range Sum Queries 題解。練習一維前綴和的基本實作，快速計算多次區間查詢。

6. 題解：森林查詢

#

CSES Forest Queries 題解。進階至二維前綴和，解決矩陣內的區域求和問題。

7. 題解：拿破崙蛋糕

#

Codeforces Napoleon Cake 題解。練習差分技巧在區間覆蓋與修改上的應用，處理多層操作的累積效應。

8. 題解：餐廳顧客

#

CSES Restaurant Customers 題解。利用差分或掃描線的概念，解決時間區間重疊的最大值問題。