1707. Maximum XOR With an Element From Array
解題說明
Maximum XOR With an Element From Array
題目描述：給定整數陣列 nums 和查詢陣列 queries，每個查詢 queries[i] = [xi, mi]，求 xi XOR nums[j] 的最大值，其中 nums[j] <= mi。若不存在滿足條件的 nums[j]，回傳 -1。
解題思路（離線排序 + 二進位 Trie）：
若對每個查詢獨立建 Trie，時間為 O(n · q)，會超時。關鍵觀察：若先按 mi 升序排序查詢，再同步按升序將 nums 中 <= mi 的元素插入 Trie，每個元素只需插入一次。
演算法步驟：
- 將
queries按mi升序排序（記錄原始索引）；nums也排序。 - 用指針
j追蹤下一個要插入 Trie 的nums元素。 - 對每個查詢
(xi, mi)：- 插入所有
nums[j] <= mi的元素到 Trie（j++）。 - 若 Trie 為空（沒有合法元素），記錄 -1。
- 否則，在 Trie 中貪心求最大 XOR：從最高位元（bit 30）到最低位，盡量選與
xi當前位元相反的分支。
- 插入所有
- 按原始索引還原答案。
二進位 Trie 節點只有 children[2]（代表 bit 0 或 1），最多 31 層（覆蓋 30 位非負整數）。
C++ 解法
複雜度分析
時間複雜度：O((n + q) log n + n · 31 + q · 31) — 排序 nums 和 queries 各 O(n log n) 和 O(q log q)；每個 nums 元素插入 Trie 一次 O(31)；每個查詢在 Trie 中搜尋 O(31)；整體為 O((n + q) log(n + q))。
空間複雜度：O(n · 31) — Trie 最多 n × 31 個節點（每個元素 31 位，每位一個節點）。
虛擬碼
1. Sort nums ascending.
2. Sort query indices by mi ascending.
3. Initialize Trie with single root node, pointer j = 0.
4. For each query index idx in sorted order:
a. While j < len(nums) and nums[j] <= mi: insert(nums[j]); j++.
b. If j == 0: ans[idx] = -1.
c. Else: ans[idx] = query(xi) // Greedy max XOR in trie.
5. Return ans.
query(num):
For bit from 30 down to 0:
want = 1 - ((num >> bit) & 1)
If trie has child[want]: take it, result |= (1 << bit).
Else: take child[1-want].其他解法
方法二：暴力枚舉
對每個查詢，線性掃描所有 nums[j] <= mi 的元素，計算 XOR 取最大值。時間 O(n · q)，空間 O(1)。當 n = q = 10⁵ 時有 10¹⁰ 次操作，嚴重超時，僅適合驗證小測資。
方法三：線上 Trie + 動態刪除
若查詢必須線上處理，可為每個 mi 值預先建立一個「版本 Trie」（持久化 Trie），查詢時直接用 mi 對應的版本。時間 O((n + q) · 31)，空間 O(n · 31)。實作複雜，但支援線上查詢，適合強制線上的場景。
方法四：按位貪心 + 排序分組
將所有元素和查詢按照最高位分組，遞迴地對每一位決定答案的對應位。本質上是將 Trie 結構展開為遞迴分治，理論等效但實作更複雜，不如顯式 Trie 直觀。
延伸思考
- 若查詢條件改為
nums[j] >= mi（下界限制），離線策略應如何調整（降序排序）？Trie 的操作有何不同？ - 若要同時支援上界與下界限制（
li <= nums[j] <= mi），能否用持久化 Trie（Persistent Trie）解決？時間複雜度如何？ - 二進位 Trie 貪心求最大 XOR 的思路在 LC 421（Maximum XOR of Two Numbers in an Array）中也有應用，兩題的差異在哪裡？此題多了哪個維度的限制？