Range Kth Smallestに対するもう2つの解法
Published on 2025-07-12Last Modified 2025-07-12
Table Of Contents
概要
去年の9月に Range Kth Smallestに対する4つの解法と2つの実装例 というものを書いた。 あのときは4つしか解法を知らなかったが、今回さらに2つ解法を知ったので試してみた。
問題（再掲）
$N$要素の数列$A$が与えられる。$Q$個のクエリに解答せよ。
- $A$の$[l _ i, r _ i)$内にある要素の中で$k _ i + 1$番目に小さい値を答える。
$1 \leq N \leq 2 \times 10 ^ 5, \quad 1 \leq Q \leq 2 \times 10 ^ 5, \quad 1 \leq A _ i \leq 10 ^ 9$
解法5
前回の解法3で並列二分探索を紹介したが、通常のセグメント木の代わりに永続セグメント木を用いることで通常の二分探索で解ける。
まず永続セグメント木について簡単に説明をする。 永続セグメント木とは、次の操作をサポートするデータ構造である。
init(N): 永続セグメント木を長さNで初期化する。$O(N)$時間。set(ver, i, v): バージョンverのセグメント木のi番目にvをセットした新しいバージョンのセグメント木を作成する。バージョンverのセグメント木は破壊されない。$O(\log N)$時間。get(ver, i): バージョンverのセグメント木のi番目を取得する。$O(\log N)$時間。prod(ver, l, r): バージョンverのセグメント木の区間$[l, r)$に対するモノイド積を取得する。$O(\log N)$時間。
これをどう実現しているのかについては 永続セグメント木・永続遅延セグメント木 - 37zigenのHP が詳しい。
細かい解法について説明する。 元の解法においては、「$A$における小さい方から$x$個の値のある場所に1、それ以外に0をセットしたセグメント木」を考えた。 そして、$[l _ i, r _ i)$の和が初めて$k _ i$を超えた$x$はいくつか？がわかれば元の問題が解ける。 これをクエリごとに行うと間に合わないので、全クエリを並列に考えることで計算量を均していた。
さて、永続セグメント木を用いた解法を考える。
全て$0$をセットしたセグメント木をバージョン0とする。
バージョン$x$のセグメント木を「$A$における小さい方から$x$個の値のある場所に1、それ以外に0をセットしたセグメント木」とする。
1回のsetをすることでバージョン$x - 1$からバージョン$x$を作ることができるため、合計$O(N \log N)$時間で全てのバージョンを作れる。
あとは各クエリで元の解法と同じように二分探索をすれば解ける。各バージョンに直接アクセスできるため、並列二分探索は必要ない。
並列二分探索に対して優れている点は
- オンラインクエリで解ける
- 実装が極めて簡単
という2点だと思う。逆に劣っている点は
- 空間計算量が$O(\log N)$倍悪化する（ちなみに、$\log _ 2 (2 \times 10 ^ 5) \approx 18$）
- 定数倍がかなり悪い
制約が厳しいと実用的に運用するのは難しい。
並列二分探索に対して実行時間3倍、メモリ11倍になっている。
解法6
永続セグメント木・永続遅延セグメント木 - 37zigenのHP に掲載されていた解法。
あらかじめ$A$を座標圧縮しておく。
バージョン0のセグメント木はすべての場所に0がセットされているとする。 バージョン$x$のセグメント木を$1 \leq i \leq x$に対して$A _ i$に1、それ以外に0をセットしたセグメント木とする。 解法5と同様にこれも$O(N \log N)$時間でバージョン$N$まで構築できる。
実は、これらのセグメント木たちを用いると、ある区間における$A _ i$たちのみを使って作ったセグメント木をシミュレートできる。
$p < q$とする。 バージョン$p$とバージョン$q$のセグメント木を考える。各ノードには担当区間のモノイド積がのっているが、（同じ位置にあるノードの）バージョン$q$における積からバージョン$p$における積を引き算することで$A _ 1$から$A _ p$からの寄与をキャンセルすることができる。 これであたかも$A _ {p + 1}$から$A _ q$のみを使っているかのような状態を作れる。
各ノードにおいて累積和を考えているようなものだと思うとわかりやすいかもしれない。
これを用いてクエリ$[l _ i, r _ i)$に答えよう。（この先クエリは0-indexedで考える。） 上記の方法を$l _ i, r _ i$に対して適用して、$A _ {l _ i}$から$A _ {r _ i}$のみを使ったセグメント木を仮想的にシミュレートできる。（$A$の添字は1-indexedなままであることに注意。）
あとはこのセグメント木においてprod(0, x)が$k _ i$を初めて超えるような$x$が求まれば元の問題が解ける。
普通に二分探索すると$O(\log ^ 2 N)$時間だが、max_right（セグメント木上の二分探索）を行うことで$O(\log N)$時間になる。
構築で$O(N \log N)$時間、各クエリ$O(\log N)$時間なので合計$O((N + Q) \log N)$時間。
いくつか特徴をまとめると、
- 逆元が必要なので、モノイドには適用できない
- オンラインクエリで解ける
- 同じく空間$O(N \log N)$が必要
という感じになる。 この解法は解法4に似ているが、永続化と逆元を活用してMoのパートを累積和に変換しているようなイメージだと思う。
類似の解法で点追加削除なし、重み変更なしの矩形和取得をオンライン、$O(\log N)$ per queryで解ける。 こっちは座標圧縮→yの昇順に点追加しながらバージョンを変えていくと同様に累積和みたいになって解ける。 range kth smallestはMoを変換したような解法になったが、矩形和クエリは平面走査を変換したような解法になっている。 ただしこちらも空間計算量がかなりネックになる点は注意。
矩形和(永続セグメント木) | Nyaan’s Library
まあ正直領域木みたいなのを用意したほうが取り回しがよさそう。
lib/data_structure/range_tree.hpp | kyopro_library
おわりに
永続データ構造重すぎて困りました。
動的WM以外で点更新ありの解法知っている人は是非教えてください。