程式設計面試：如何用 Wavelet Matrix 支援區間第 k 小？
題干與適用場景
給定靜態整數陣列 a，需要回答大量半開區間 [l, r) 查詢：回傳第 k 小的值、區間內等於 x 的頻次，以及落在 [lo, hi) 的元素數量。陣列不更新，值域可能很大。請設計並分析一種比每次排序更快的結構。
Wavelet Matrix 將每個值按二進位位元從高到低穩定分割，在每一層保存位元向量及其前綴 1 的數量。它不需要顯式樹指標，查詢時把區間映射到下一層。高品質回答要先明確 k 是 0-based，處理座標壓縮和重複值，再給出時間與空間邊界。
面試官考察點
- 是否能說明穩定分割、零段起點與 rank 映射為何保持相對順序。
- 是否能在
[l, r)上沿位元層選出第 k 小並正確累積答案。 - 是否處理重複值、空區間、
k越界與負數值。 - 是否區分值域計數、單值頻次與第 k 小的查詢路徑。
- 是否給出
O(B)查詢、O(nB)建構和可壓縮空間的複雜度。 - 是否知道靜態結構不天然支援高效更新，以及何時應改用其他結構。
回答前需要澄清的問題
- 查詢中的
r是否為排他端點？k是從 0 還是從 1 開始？ - 陣列是否真的不會更新？若有更新，更新頻率和查詢頻率是多少？
- 值是否為有號整數，最大位寬是多少？是否可以先做座標壓縮？
- rank 查詢需要多少記憶體，是否允許分塊或 bitvector 壓縮？
- 只要第 k 小，還是還需要頻次、前驅或區間和？不同操作會改變結構選擇。
30 秒回答框架
我會把值壓縮到連續的非負編碼，設最大位寬為 B。建構時從最高位到最低位穩定地把目前序列分成 0 段和 1 段，同時保存該層的位元向量與 rank1 前綴。查詢第 k 小時維護 [l,r)，計算這一層的零數量；若 k 小於零數量就映射到零段，否則扣除零數量並進入一段，同時在答案中設定目前位元。單值頻次用兩次 rank，值域計數用兩次小於計數相減。所有查詢為 O(B)，建構為 O(nB)。
分步驟深入解答
1. 編碼值域與位寬
若值域是任意有號整數，可排序去重後映射到 0..m-1，並保存編碼到原值的陣列。這樣 B 為 ceil(log2(m))，還要處理 m 為 1 的情況。若必須保留自然數值，可對有號最高位做偏移，使按無號字典序等同於數值序。
2. 穩定分割一層
對目前序列 cur 查看第 bit 位，先把所有 0 放入 next，再把所有 1 放入 next，保持各自原有順序。位元向量 bv[i] 記錄原位置 i 的位值，zeroCount 記錄本層 0 的總數。穩定性保證後續層的區間映射仍對應原區間中的同一批元素。
rank1(i) = bv[0..i) 中 1 的數量
zeroCount = n - rank1(n)
若目前區間為 [l, r)：
zero 區間 = [l - rank1(l), r - rank1(r))
one 區間 = [zeroCount + rank1(l), zeroCount + rank1(r))3. 查詢區間第 k 小
每層先計算 zeros = (r-l) - (rank1(r)-rank1(l))。當 k 小於 zeros 時，把 [l,r) 映射到零區間；否則令 k -= zeros，把區間映射到一段，並把答案的目前位元設為 1。處理完 B 層後得到編碼，再反向映射為原值。
4. 單值頻次
把目標值的每一位當作固定分支，按同樣的映射更新 [l,r)。如果某一位目標為 0，進入零區間；為 1，進入一段並加上 zeroCount。完成 B 層後，區間長度就是該值在原區間中的頻次。目標值不在壓縮表時直接回傳 0。
5. 值域計數
定義 countLess(x, l, r) 回傳 [l,r) 中小於 x 的元素數。沿位元層比較 x 的目前位元：當 x 的位元為 1 時，目前區間的全部零分支都小於 x，應把 zeros 加入答案，然後繼續一分支；為 0 時只繼續零分支。因此 [lo, hi) 的計數為 countLess(hi)-countLess(lo)。
6. 邊界與驗證
空區間和左端點不小於右端點時，應明確回傳錯誤或 0，不能讓 rank 陣列越界。k 必須落在目前區間長度以內。測試應涵蓋全部值相同、嚴格遞增、重複交錯、負數、單元素、最大值位寬和壓縮表外查詢，並與樸素排序或計數結果逐條比對。
7. 複雜度與取捨
若使用普通前綴陣列，每層占 O(n) 個計數，空間 O(nB)，建構 O(nB)，每個操作 O(B)。將位元向量換成支援 rank 的壓縮 bitvector 可降低常數和空間。結構適合靜態、多查詢場景；需要頻繁更新時，可考慮分塊 Wavelet Matrix、線段樹套有序結構或離線演算法，並重新評估記憶體和更新成本。
高品質示範回答
我先明確查詢使用半開區間，k 從 0 開始，陣列不更新。值先做座標壓縮，B 是編碼的位寬。建構時從高位到低位穩定分割，並為每層保存位元向量的 rank1 前綴和零段長度。
第 k 小查詢在每層計算目前區間的零數量。k 落在零段就用 l-rank1(l) 和 r-rank1(r) 映射；否則扣除零數量，映射到 zeroCount+rank1(l) 與 zeroCount+rank1(r)，並設定答案位元。單值頻次沿固定值路徑，值域計數用兩個 countLess 相減。建構和每次查詢分別是 O(nB) 與 O(B)，越界和壓縮表外值回傳明確錯誤或 0。
常見錯誤
- 混用閉區間和半開區間 → rank 偏移一位 → 統一使用
[l,r)並寫出映射式。 - 忘記穩定分割 → 下一層區間不再對應原元素 → 0 段和 1 段都保持原順序。
- 選擇一段時沒有扣除零數量 → 第 k 小結果偏大 → 先
k -= zeros再進入一段。 - 直接把有號數按無號位序比較 → 負數順序錯誤 → 做座標壓縮或翻轉符號位。
- 把結構當成支援更新 → 更新會破壞每層排列 → 說明靜態前提並選擇動態替代方案。
- 只測不同值 → 重複值和邊界錯誤被隱藏 → 加入全相同、交錯重複、空區間和越界測試。
追問及應對
為什麼不用每次排序？
單次排序需要 O((r-l) log(r-l))，大量查詢會重複工作。Wavelet Matrix 預先編碼每一層的分支，查詢只走 B 層，適合靜態資料和高查詢量。
rank1 為什麼能完成區間映射？
前綴 rank 給出區間左右端點之前的一段中有多少個 1，因此能分別計算該區間在零段和一段中的相對位置；穩定分割保證這些位置對應同一批元素。
如何支援第 k 大？
把 k 轉成區間長度減一再減去 k 的第 k 小，或在每層優先走一分支並相應扣除一數量。兩種方式都保持 O(B)。
如果值域遠大於 n 怎麼辦？
對出現值做座標壓縮，並保存編碼到原值的映射；查詢未出現的值透過二分映射到邊界或直接回傳頻次 0。
需要動態更新時怎麼辦？
普通 Wavelet Matrix 不適合頻繁更新。可採用分塊重建、帶動態 bitvector 的結構或離線處理；選擇取決於更新與查詢比例、延遲目標和記憶體預算。