1. 概要 本記事では，静的な列に対する区間クエリを高速に処理するデータ構造である Disjoint Sparse Table （DST と略記することもあります）を解説します． Disjoint Sparse Table は，長さ $N$ の列に対して事前計算 $\mathrm{O}(N\log N)$ 時間を行うこ…

1. 概要 通常のセグメント木は，更新を行うたびに古い状態を破棄し，常に最新のバージョンだけを保持する構造になっています．それに対して 永続セグメント木 は，過去のすべてのバージョンに対してアクセスや更新が可能なセグメント木です． 永続セグメント…

1. 概要 本記事では，静的な配列に対するある種の区間クエリを高速に処理するデータ構造であるスパーステーブル（Sparse Table）を解説します． スパーステーブルは，事前計算に $\mathrm{O}(N\log N)$ 時間を使うことで，区間最小値などのクエリに $\mathrm…

1. 概要 本記事では，Sqrt Tree について解説します． Sqrt Tree は列の平方分割を再帰的に行うことでできる木構造です．特に静的なモノイド列に対する区間積クエリを高速に処理できます．具体的には，列の長さを $N$ とするとき，事前計算 $\mathrm{O}(N\lo…

1. 概要 本記事では Sqrt Tree などに続き，再び静的なモノイド列に対する区間積クエリの問題を扱います． 特に，長さ $N$ の列について $\mathrm{O}(N)$ 時間の事前計算を前提とした場合，クエリあたり $\mathrm{O}(\alpha(N))$ 時間（$\alpha(N)$ は逆アッ…

1. 概要 Wavelet Matrix の基礎的な理解や実装方法については， Wavelet Matrix（基礎） で解説しました． 本記事では改めて，Wavelet Matrix を使うとどのような処理をできるのかについて，具体的な例をいくつか確認します． なおほとんどの例について，Wav…

1. 概要 本記事では，Wavelet Matrix というデータ構造について解説します。 Wavelet Matrix とは大雑把に言えば，静的な非負整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ に対して，クエリ $(L,R)$ が与えられるたびに，「多重集合 $\lbrace A _ L, A _ {L + 1}, \…