push_back / suffix の xor 基底クエリ Θ(log(A))

概要

最初空の数列 $A$ があり、以下のクエリを処理するアルゴリズムを説明する。

$x$ が与えられ、 $A$ の末尾に $x$ を追加する。
が与えられ、の xor に関する基底を出力する。
- ただし $x$ の highest set bit を $\operatorname { bsr } \left ( x \right ) := \max \left \lbrace k \mathrel { } \middle \vert \mathrel { } x _ k = 1 \right \rbrace$ と定義したとき $\operatorname { bsr } \left ( b _ j \right )$ は $j$ について単調減少である。

時間計算量はいずれも $\Theta \left ( \log \left ( \max A \right ) \right )$ である。

アルゴリズム

$0 \leq x \lt 2 ^ w$ のクエリだけが与えられるとして、各クエリを $\Theta \left ( w \right )$ で処理するアルゴリズムを説明する。多少工夫すれば $w$ を各クエリ時点での $\log \left ( \max A \right )$ に合わせることもできる。

基本となる操作は $l \lt r$ に対する $A _ l \leftarrow A _ l \oplus A _ r$ という操作である。 $A$ のいかなる suffix に着目してもこの操作は基本変形になっているから、この操作だけを行っている限りは $\operatorname { span } \left \lbrace A _ i , A _ { i + 1 } , \dots \right \rbrace$ は変化しない。

$A$ の添え字の列 $\left ( i _ 0 , i _ 1 , \dots , i _ { w - 1 } \right )$ を管理する。これらは以下の不変条件を維持する。

$\operatorname { bsr } \left ( A _ { i _ k } \right ) = k$
$i _ k$ として現れない $i$ について $A _ i = 0$

$A$ が最初からいくつかの要素を持っていてもクエリには影響しないため、最初 $A = \left ( 2 ^ 0 , 2 ^ 1 , \dots , 2 ^ { w - 1 } \right )$ として $i _ k = k$ とすれば条件を満たす。 $A = \left ( A _ 0 , A _ 1 , \dots , A _ { n - 1 } \right )$ の末尾に要素を追加した場合、以下の処理を実行し不変条件を回復する。

\begin{align} & j := n \cr & \mathtt { for } ~ k := w - 1 ~ \mathtt { to } ~ 0 \cr & \quad \quad \mathtt { if } ~ \left ( A _ j \right ) _ k = 0 \cr & \quad \quad \quad \quad \mathtt { continue } \cr & \quad \quad \mathtt { if } ~ j \gt i _ k \cr & \quad \quad \quad \quad \left ( j , i _ k \right ) \leftarrow \left ( i _ k , j \right ) \cr & \quad \quad A _ j \leftarrow A _ j \oplus A _ { i _ k } \end{align}

アルゴリズムの正当性は以下の事実に着目することで確認できる。

ループの始まりでは $\operatorname { bsr } \left ( A _ j \right ) \leq k$ であり、ループの終わりでは $\operatorname { bsr } \left ( A _ j \right ) \lt k$ である。
不変条件が、 $A _ j \neq 0$ となり得ることを除き常に満たされている。
$A$ を変更する操作は、 $l \lt r$ に対する $A _ l \leftarrow A _ l \oplus A _ r$ の形でしか行われていない。

処理の終わりでは $A _ j = 0$ となっているから、不変条件が完全に満たされる。 $\left \lbrace A _ i , A _ { i + 1 } , \dots \right \rbrace$ の基底は $\left \lbrace A _ { i _ k } \mathrel { } \middle \vert \mathrel { } i \leq i _ k \right \rbrace$ であるから、ただ出力すればよい。

実際には $A$ を陽には管理せず、 $\left ( i _ k , A _ { i _ k } \right )$ を管理すると空間計算量が抑えられる。

応用

区間 xor 基底クエリ

静的な区間 xor 基底クエリが $\Theta \left ( \left ( N + Q \right ) \log \left ( \max A \right ) \right )$ で処理できる。 $A _ 0 , A _ 1 , \dots , A _ i$ まで処理したときの $\left ( i _ k , A _ { i _ k } \right )$ を全て保持しておけば、オンラインクエリにも対応可能。

実装例

木上のパス xor 基底クエリ

静的な木上のパス xor 基底クエリが $\Theta \left ( N \log \left ( \max A \right ) + Q \left ( \log \left ( \max A \right ) \right ) ^ 2 \right )$ で処理できる。自由に根を決め、根から各頂点までのパスについての $\left ( i _ k , A _ { i _ k } \right )$ を計算しておく。これは各 $v$ について、根から $v$ の親へのパスに対する $\left ( i _ k , A _ { i _ k } \right )$ に $a _ v$ を push すればいいので $\Theta \left ( N \log \left ( \max A \right ) \right )$ で計算できる。 $uv$ パスに対するクエリにおいては、 $\operatorname { LCA } \left ( u , v \right )$ から $u , v$ それぞれへのパスの xor 基底をマージすればよい。それぞれは根から $u , v$ へのパスの suffix であるから本稿のアルゴリズムで求めることができる。

実装例 (LCA の計算に $\Theta \left ( \log \left ( N \right ) \right )$ のアルゴリズムを使っているので計算量は少し増えている)

拡張

アルゴリズムを観察すると、要素の追加が末尾である必要はないことが分かる。すなわち、最初 $S = \emptyset$ として、以下のクエリを処理できる。

$j , x$ が与えられ、 $S \leftarrow S \cup \left \lbrace \left ( i , x \right ) \right \rbrace$
が与えられ、の xor に関する基底を出力する。
- ただし $\operatorname { bsr } \left ( b _ k \right )$ は $k$ について単調減少である。

noshi91のメモ

データ構造のある風景

push_back / suffix の xor 基底クエリ Θ(log(A))

概要

アルゴリズム

応用

区間 xor 基底クエリ

木上のパス xor 基底クエリ

拡張