はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるマージテク問題まとめ

マージテク

  • 正式名称、データ構造をマージする一般的なテク
  • 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN)
  • 発祥の地
  • 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがある(O(log^2N),Skew HeapだとO(logN))

hamayanhamayan.hatenablog.jp

【発展的話題】Sack (dsu on tree)