プロンプトとスコープ
静的な整数配列 a が与えられたとき、多数の半開区間クエリ [l, r) に応答します。k 番目に小さい値、x の出現頻度、および [lo, hi) 内の要素数を返します。配列は変更されず、値は大きくなる可能性があります。各区間をソートするよりも高速なデータ構造を設計し、分析してください。
ウェーブレット行列（wavelet matrix）は、最上位ビットから最下位ビットに向かって値を安定的に分割し、各レベルでビットベクトルとプレフィックスの 1 の個数を保持します。明示的なツリーポインタは不要であり、各クエリはその区間を次のレベルへとマッピングします。k が 0-indexed であることを明示し、座標圧縮や重複を扱い、境界条件を示してください。
面接官が評価するポイント
- 安定分割、0-ブロックの開始位置、および rank マッピングが順序を維持する理由を説明できるか。
[l, r)上で k 番目の値を選択し、ビットを正しく蓄積できるか。- 重複、空の区間、範囲外の
k、および符号付きの値を処理できるか。 - 値域カウント、特定値の頻度、および k 番目クエリの探索経路の違いを区別できるか。
O(B)のクエリ時間、O(nB)の構築時間、および圧縮可能な空間計算量の境界を示せるか。- 静的構造では低コストな更新が提供されないことを認識し、代替案を知っているか。
明確化のための質問
rは開区間端点（含まない）ですか？また、kは 0-indexed ですか、それとも 1-indexed ですか？- 配列は真に不変ですか？そうでない場合、更新とクエリの頻度はどの程度ですか？
- 値は符号付きですか？最大ビット幅はいくつですか？座標圧縮は可能ですか？
- rank 用に利用可能なメモリはどの程度ですか？ビットベクトルのブロック化や圧縮は可能ですか？
- 必要なのは k 番目のみですか？それとも頻度、先行要素、区間和なども必要ですか？操作によって選択が変わります。
30秒での回答例
値をビット幅 B の非負コードに座標圧縮します。構築時は、現在のシーケンスを最上位ビットから順に安定分割し、各レベルのビットベクトルとプレフィックスの rank-one カウントを保存します。k 番目のクエリでは、[l,r) を保持してそのレベルでの 0 の個数を数え、0-ブロックにマッピングするか、0 の個数を減算して 1-ブロックにマッピングしつつ対応する回答ビットを立てます。頻度は 2 回の rank 走査を使用し、値域カウントは 2 回の countLess 呼び出しの差分となります。クエリ計算量は O(B)、構築計算量は O(nB) です。
ステップバイステップの解決策
1. 値の領域をエンコードする
任意の符号付き整数の場合、重複を除いた値をソートして 0..m-1 にマッピングし、コードから元の値への配列を保持します。このとき B は ceil(log2(m)) となり、m=1 の明示的なケースを処理します。自然な順序を直接保持する必要がある場合は、符号付きの値を符号なしとして扱う前に符号ビットを反転させます。
2. 1つの安定したレベルを構築する
bit の cur を検査し、ビットが 0 のすべての値を next に追加した後、ビットが 1 のすべての値を追加して、両グループ内の相対順序を保持します。bv[i] は元の位置 i でのビットを記録し、zeroCount は 0 の個数となります。安定性により、以降の区間が元の同じ要素に正しく紐付けられます。
rank1(i) = number of ones in bv[0..i)
zeroCount = n - rank1(n)
for interval [l, r):
zero interval = [l - rank1(l), r - rank1(r))
one interval = [zeroCount + rank1(l), zeroCount + rank1(r))3. 区間内の k 番目の値をクエリする
各レベルで zeros = (r-l) - (rank1(r)-rank1(l)) を計算します。k が 0 の個数より小さい場合は、0 の区間にマッピングします。そうでない場合は、0 の個数を減算し、1 の区間にマッピングして、現在の回答ビットを立てます。B レベル進んだ後、コードを元の値にデコードします。
4. 単一値の出現頻度をクエリする
ターゲットの各ビットを固定の分岐として扱い、[l,r) を同様にマッピングします。ターゲットのビットが 0 の場合は 0 の区間に進み、1 の場合は zeroCount を使って 1 の区間に進みます。B レベル進んだ後の区間の長さが頻度になります。圧縮辞書に存在しないターゲットの場合は 0 を返します。
5. 値の範囲をクエリする
[l,r) 内で x 未満の値の個数を countLess(x, l, r) と定義します。x の対象ビットが 1 であるレベルでは、0 への分岐はすべて x より小さいため、zeros を加算して 1 の分岐に進みます。ビットが 0 の場合は、0 の分岐にのみ進みます。[lo, hi) 内の個数は countLess(hi)-countLess(lo) となります。
6. 境界条件と検証
空の区間や、左端点が右端点以上の場合の動作を定義します。rank 配列の範囲外を決して参照しないようにします。k が現在の区間の長さの中に収まっていることを要求します。すべて同一値、ソート済み、インターリーブされた重複、負の値、1 要素の区間、最大ビット幅、辞書に存在しない値などをテストし、各結果をブルートフォースのソートやカウントと比較します。
7. 計算量とトレードオフ
通常のプレフィックスカウントを使用すると、各レベルは O(n) 個のカウンタを格納するため、空間計算量と構築計算量は O(nB) となり、すべての操作は O(B) です。rank 操作をサポートする圧縮ビットベクトルを使用すると、空間と定数倍が削減されます。この構造は不変でクエリ頻度が高いワークロードに適しています。更新が必要な場合は、ブロックごとの再構築、動的ビットベクトル、順序付き集合のセグメント木、またはオフライン処理を検討し、メモリと更新コストを再評価してください。
優れた回答の例
区間は半開区間であり、k は 0-indexed で、配列は不変であると前提を置きます。値を座標圧縮し、B ビットを使用します。構築では最上位ビットから順に安定分割を行い、各レベルでプレフィックスの rank-one カウントと 0-ブロックの長さを保持します。
k 番目クエリでは、各レベルで現在の区間内の 0 の個数を数えます。k が 0 の個数に含まれる場合は l-rank1(l) および r-rank1(r) でマッピングし、そうでない場合は 0 の個数を減算して zeroCount+rank1(l) および zeroCount+rank1(r) でマッピングして回答ビットを立てます。頻度は固定値のパスをたどり、値域カウントは 2 回の countLess 呼び出しです。構築は O(nB)、各クエリは O(B) であり、無効な区間や存在しないコードには明示的なエラーまたは 0 を返します。
よくある間違い
- 閉区間と半開区間を混同する → rank が 1 つずれる →
[l,r)を一貫して使用し、マッピングを記述する。 - 安定分割を忘れる → 以降の区間が同じ要素を特定できなくなる → 両方のブロックで順序を保持する。
- 0 の個数を減算せずに 1-ブロックに入る → k 番目の値が大きくなりすぎる → マッピング前に減算する。
- 符号付きの値を符号なしビットとして比較する → 負の数の順序が崩れる → 座標圧縮するか符号ビットを反転させる。
- 更新が低コストであると思い込む → 更新によってレベルごとの順列が無効になる → 静的な前提条件と代替案を明記する。
- 重複のない値のみでテストする → 重複や境界条件のバグが見落とされる → 同一要素、インターリーブ、空区間、無効なケースをテストする。
フォローアップの質問と回答
なぜ各区間をソートしないのですか？
1つの区間をソートするコストは O((r-l) log(r-l)) であり、クエリ間で作業が重複します。ウェーブレット行列は分岐情報を事前計算するため、クエリは B レベルを訪れるだけで済み、静的でクエリ数の多いワークロードに適しています。
なぜ rank1 で区間がマッピングされるのですか？
プレフィックス rank は各端点より前に出現する 1 の個数を示すため、0-ブロックおよび 1-ブロックにおけるその区間の相対的な位置が分かります。安定分割により、それらの位置が同じ要素を表すことが保証されます。
k 番目に大きい値にはどう答えますか？
length - 1 - k で k 番目に小さい値に変換するか、各レベルで 1 の分岐を優先しつつそのカウントを減算します。どちらも O(B) のままです。
値の領域が n よりはるかに大きい場合はどうしますか？
出現した値を座標圧縮し、逆引きマップを保持します。クエリされた未知の値については、挿入境界を二分探索するか、頻度 0 を返します。
更新が必要な場合はどうしますか？
プレーンなウェーブレット行列は更新に適していません。更新とクエリの比率、レイテンシ目標、メモリに応じて、ブロック分割による再構築、動的ビットベクトル、順序付き構造のセグメント木、またはオフライン処理を使用します。