概要 人によって実装が大きく分かれることに定評のある全方位木DPですが、私のスタイルの内容と、その背景をご紹介します。なおプログラミング言語特有の設計のお話は、好みが分かれるところだと思いますためこの記事では敢えて省いております。 内容 次のコ…

概要 $\pm 1$-RMQ 問題に代表されるように、桁数付きのビットパターンをキーにした前計算テーブルが必要なことがよくありますが、そのまま整数の $2$ 進展開と解釈してしまうと長さの違いが同一視されてしまいます。これを回避するキレイな方法をご紹介し、…

概要 HL 分解（重軽分解, HL Decomposition, Heavy-Light Decomposition）には、与えられたパスを heavy path に含まれる path に分解する機能を付けると便利ですが、LCA を含むかどうか（いわゆる節点/辺イテレータ）、非可換なことをしたいときのパスの方…