木上の Disjoint Sparse Table

概要

$n$ 頂点の木の各頂点にモノイド $M$ の元 $a _ v$ が乗っているとして、指定されたパス上の値の総積を計算するクエリが、前計算 $\Theta \left ( n \log \left ( n \right ) \right )$ 、クエリ $\Theta \left ( 1 \right )$ で処理できる。

アルゴリズム

重心分解を行う。

木の重心を $c$ とし、各 $v \in V$ に対して、 $c v$ パスから $c$ を除いたものに対するクエリ結果を計算しておく *1 。 $u v$ パスが $c$ を含む場合、 $u v$ パスに対するクエリはこの前計算を用いて $\Theta \left ( 1 \right )$ で計算できる。 $c$ を含まない場合に対処するため、木から $c$ を取り除くことで得られる部分木たちに対し再帰的に同様の前計算を行う。

クエリとして $u , v$ が与えられた際に適切な $c$ を発見するためには、重心分解によって得られた木構造において LCA を計算すればよい。 (Disjoint) Sparse Table を用いた、前計算 $\Theta \left ( n \log \left ( n \right ) \right )$ 、クエリ $\Theta \left ( 1 \right )$ の LCA があるためそれを用いる。

良い性質

一般の $x , y \in M$ に対する $x y$ の計算はクエリの際に $1$ 度行われるだけで、前計算はすべて $x \in M, v \in V$ に対する $x a _ v , a _ v x$ の計算を用いている。よって、この種の計算が通常より高速に行える状況では計算量が改善する。例: 各頂点に非負整数が定められており、パス上の非負整数に対する xor 基底をクエリで求めたい場合。

これは Disjoint Sparse Table も持つ性質である。そもそも Disjoint Sparse Table はこのデータ構造をパスグラフに対して適用したものと一致する。したがってこのデータ構造は Disjoint Sparse Table の一般化であると見ることもできる。

LCA を計算する部分の対案

本稿のデータ構造でクエリを行う際に $c$ を計算する部分は、Disjoint Sparse Table においては整数の xor と bsr で行っていた。 1/3 重心分解などを用いて LCA を計算したい木を二分木にし、根から $v$ までのパスの左右を 01 でエンコードすれば、同様に xor と bsr で LCA を計算できる。正確には LCA ではなく LCA の深さが求まるが、そもそも前計算のデータを (頂点, 深さ) に対してデータを対応させるような形式で管理しておけばよい。