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

hamayanhamayan's blog

競技プログラミングにおける分割統治法問題まとめ

分割統治法

  • 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」
  • 色んな分割統治法があるが、大体空間サイズが半分になってlogNくらいで解けるようになる
  • 再帰的な定義がなされているやつを再帰的に処理して解決する問題もある
  • 列の分割統治法はセグメントツリーでの別解がよくある印象
  • 木の分割統治法では「重心分解」が有名