rmq

最近公共祖先(LCA):離線&線上演算法

問題:求兩個結點的最近公共祖先(即在樹中的公共祖先中高度最低的祖先),下面介紹兩種適用於不同場景的演算法。   Hiho15:離線Tarjan演算法 基本思想 Tarjan演算法適用於離線批量處理多個查詢請求。基本思想是以深度優先搜尋的順序訪問這顆樹,給這棵樹的結點染色,一開始所有結點都是白色的,而 […]

  • 2018.06.05
  • ,

rmq_ST模板

某線段最值: /* rmq: ST: minn[i][j]表示從第i個到i (1<<j)-1的最小值 狀態方程:minn[i][j]=min(minn[i][j-1],minn[i (1<<(j-1))][j-1]) 查詢[l,r]區間時,區間個數是r-l 1,k為log2( […]