3845. 最大子數組亦或值

前置題目：421. 數組中兩個數的最大異或值, 239. 滑動窗口最大值

思路

先利用 239 題當中的方式，找到區間的最大跟最小值，讓字典樹當中的數值只保留這段區間內的數值，
再利用 421 題的方式找到最大的Xor數值，因為要找的是連續子陣列的和，所以用前綴和記錄前綴xor。

程式碼

前綴和 + 字典樹 + 雙端隊列

struct TrieNode {
    int pass;
    TrieNode* nexts[2];
    TrieNode() : pass(0), nexts{nullptr} {}
};
class Trie {
private:
    int high;
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
        high = 16;
    }
    void insert(int x) {
        TrieNode* cur = root;
        cur->pass++;
        for(int i = high; i >= 0; i--) {
            int path = (x >> i) & 1;
            if(cur->nexts[path] == nullptr) {
                cur->nexts[path] = new TrieNode();
            }
            cur = cur->nexts[path];
            cur->pass++;
        }        
    }
    int maxXorValue(int x) {
        int res = 0;
        TrieNode* cur = root;
        for(int i = high; i >= 0; i--) {
            int path = (x >> i) & 1;
            int want = path ^ 1;
            if(cur->nexts[want] == nullptr || cur->nexts[want]->pass == 0) {
                want ^= 1;
            }
            res |= (path ^ want) << i;
            cur = cur->nexts[want];
        }
        return res;
    }
    void remove(int x) {
        TrieNode* cur = root;
        cur->pass--;
        for(int i = high; i >= 0; i--) {
            int path = (x >> i) & 1;
            cur = cur->nexts[path];
            cur->pass--;
        }
    }
};
class Solution {
public:
    int maxXor(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> preXor(n + 1);
        for(int i = 0; i < n; i++) {
            preXor[i + 1] = preXor[i] ^ nums[i];
        }
        
        Trie trie;
        deque<int> mn_q, mx_q;
        int res = 0;
        for(int l = 0, r = 0; r < n; r++) {
            trie.insert(preXor[r]);
            while(!mx_q.empty() && nums[mx_q.back()] <= nums[r]) {
                mx_q.pop_back();
            }
            mx_q.push_back(r);
            while(!mn_q.empty() && nums[mn_q.back()] >= nums[r]) {
                mn_q.pop_back();
            }
            mn_q.push_back(r);
            while(l != r && nums[mx_q.front()] - nums[mn_q.front()] > k) {
                if(mx_q.front() == l) mx_q.pop_front();
                if(mn_q.front() == l) mn_q.pop_front();
                trie.remove(preXor[l]);
                l++;
            }
            // l, l + 1, ... r - 1 都要算到
            res = max(res, trie.maxXorValue(preXor[r + 1]));
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$