1am9trash/Algorithm

算法筆記

算法筆記

• 發起時間：2021/02/14

• 背景介紹：由大學開始接觸程式，大半靠著網路上的資源自學，大二因緣際會下，參與了ACM競賽，經過一學期的磨練後，無論是對演算法的理解，還是程式的碼風都有大幅的改變，因此想透過筆記的形式好好梳理一次掌握的算法，也在未來了解新的算法時，記錄自己學習的歷程。

• 更新：

  更新日期	分類	算法
  2021/02/14	數據結構	樹狀數組
  2021/02/15	數據結構	並查集與種類並查集
  2021/02/16	數據結構	線段樹
  2021/02/17	其他	離散化
  2021/02/17	數據結構	st表
  2021/02/19	數據結構	分塊
  2021/03/01	分治	三分搜尋
  2021/03/06	數論	質數篩法
  2021/03/08	數論	擴展歐幾里德與模逆元
  2021/08/12	幾何	兩圓交點
  2021/09/19	幾何	判斷點在多邊形內

• 每個算法標題為該算法的筆記，下方的連結為模板code

• 數據結構

  1. 樹狀數組
     • 樹狀數組區間和
     • 樹狀數組區間極值
  2. 並查集與種類並查集
     • 並查集
     • 種類並查集
  3. 線段樹
     • 線段樹區間和
  4. st表
     • st表區間極值
  5. 分塊
     • 分塊區間和（偽線段樹）

• 數論

  1. 質數篩法
     • 埃式篩法
     • 線性篩法
  2. 擴展歐幾里德與模逆元
     • 擴展歐幾里德
     • 模逆元

• 分治

  1. 三分搜尋
     • 三分搜極值端點

• 幾何

  1. 兩圓交點
     • 兩圓交點
  2. 判斷點在多邊形內
     • 判斷點在多邊形內

• 其他

  1. 離散化
     • 離散化