3845. Maximum Subarray XOR with Bounded Range
解題說明
Maximum Subarray XOR with Bounded Range
題目描述：給定一個整數陣列 nums 和兩個整數 minLen 和 maxLen，找出長度在 [minLen, maxLen] 範圍內的子陣列，使得該子陣列所有元素的 XOR 值最大。回傳該最大 XOR 值。
解題思路：利用前綴 XOR 轉化。令 prefix[i] = nums[0] XOR nums[1] XOR ... XOR nums[i-1]，則子陣列 nums[l..r] 的 XOR 為 prefix[r+1] XOR prefix[l]。問題轉化為：找兩個索引 i < j，使得 minLen <= j - i <= maxLen 且 prefix[j] XOR prefix[i] 最大。
使用 Trie（二進位字典樹）來最大化 XOR。固定右端點 j，合法的左端點 i 在 [j - maxLen, j - minLen] 範圍內。需要一個支援「插入」和「刪除」的 Trie（帶計數），用滑動窗口維護合法的 prefix 值。每次右移 j 時，插入新的合法前綴值，移除過期的前綴值，然後在 Trie 中查詢與 prefix[j] XOR 最大的值。
C++ 解法
複雜度分析
時間複雜度：O(n * B) — n 為陣列長度，B 為位元數（通常 30）。每個前綴值的插入、刪除、查詢各 O(B)。
空間複雜度：O(n * B) — Trie 最多 O(n) 條路徑，每條 O(B) 個節點。
虛擬碼
1. Compute prefix XOR array: prefix[0] = 0, prefix[i+1] = prefix[i] ^ nums[i]
2. Build a Trie with insert(val, +1/-1) and queryMax(val)
3. Sliding window over valid left endpoints:
a. For j from minLen to n:
- Insert prefix[j - minLen] into Trie (add count)
- Remove prefix[j - maxLen - 1] if valid (subtract count)
- Query Trie for max XOR with prefix[j]
- Update answer
4. Return answer其他解法
分塊法 + Trie：將前綴值分塊處理，每塊建一個 Trie。查詢時合併多個塊的 Trie 結果。適合離線處理但實作複雜。
暴力枚舉 O(n² * B)：枚舉所有合法長度的子陣列，計算 XOR。在 n 較大時不可行，但可作為驗證基準。
持久化 Trie O(n * B)：使用持久化 Trie 支援「查詢版本 [l, r] 範圍內的最大 XOR」。每個版本對應一個前綴值的插入。空間消耗更大但支援更靈活的查詢。
延伸思考
- 如果長度限制改為 [minLen, infinity)（只有下界），如何簡化？
- 若需要回傳最大 XOR 對應的子陣列起止索引，如何在 Trie 中記錄索引資訊？
- 若陣列元素可以為負數（考慮 32 位元有號整數的 XOR），如何處理最高位的符號位？