# 幾個常見的時間複雜度優化小技巧
---
## 1. 用陣列儲存資訊
----
我們可以使用陣列儲存和索引值有關的資訊，紀錄完後，就可以直接根據索引值以 O(1) 時間拿到我們要的資訊。
* 基礎題：[計算數字個數](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/H)
* 挑戰題：[平均距離](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/I)
---
## 2. 預處理
----
* 例題：連續和問題([CSES 1646 Static Range Sum Queries](https://cses.fi/problemset/task/1646))
* 這種在回答所有詢問前先做一些處理的技巧被稱為「預處理」(preprocessing)。
----
* [CSES 1646 Static Range Sum Queries](https://cses.fi/problemset/task/1646) 的 [參考程式碼](https://cses.fi/paste/a04b0442689c1c591cb17b/)
---
## 3. 使用離線演算法
----
* 例題：[經典區間詢問問題 2](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/L)
* 這種先把所有詢問儲存下來後再一起處理的演算法被稱為「離線演算法」(offline algorithm)，若每讀入一個詢問就馬上算出答案後在讀入下個詢問則被稱為「在線演算法」(online algorithm)。
----
可在 [Atcoder Beginner Contest 248 D 題老師的上傳紀錄](https://atcoder.jp/contests/abc248/submissions/31003051) 參考此演算法的實作。
{"metaMigratedAt":"2023-06-16T23:18:45.060Z","metaMigratedFrom":"YAML","title":"幾個常見的時間複雜度優化小技巧","breaks":true,"slideOptions":"{\"transition\":\"fade\",\"parallaxBackgroundImage\":\"https://i.imgur.com/jtMhsLP.png\",\"parallaxBackgroundHorizontal\":200,\"parallaxBackgroundVertical\":200}","description":"我們可以使用陣列儲存和索引值有關的資訊，紀錄完後，就可以直接根據索引值以 O(1) 時間拿到我們要的資訊。","contributors":"[{\"id\":\"ec58fb73-fce8-4e38-b318-d00e84653449\",\"add\":2315,\"del\":1220}]"}