Chương 41 - Bitmask kết hợp Trie

Khi bài cần “max XOR” với số trong array, ta build Trie binary của các số (mỗi bit là 1 cấp). Query max XOR là DFS greedy đi theo bit “khác” với số hiện tại.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Binary Trie cho int 32-bit: mỗi node có 2 children (0, 1).
• Max XOR query: DFS greedy đi theo bit ngược lại.
• Trie có remove (đếm count mỗi node) cho sliding window XOR.
• Offline sort + Trie cho query với constraint giá trị.

Khi nào dùng pattern này?

• Tìm max/min XOR cặp.
• Bài với constraint trên XOR.
• Truy vấn XOR offline (sort query rồi insert dần).

Template code

Lưu ý: mỗi ### Code Python 3 bên dưới đều standalone - copy nguyên block vào LeetCode chạy được. Nếu chỉ cần template tham khảo, dùng class này:

class BinaryTrie:
    """Binary Trie cho int 32-bit. Hỗ trợ insert / max_xor."""

    def __init__(self):
        self.children = [None, None]    # 0, 1

    def insert(self, x: int, bits: int = 31) -> None:
        node = self
        for b in range(bits, -1, -1):
            bit = (x >> b) & 1
            if not node.children[bit]:
                node.children[bit] = BinaryTrie()
            node = node.children[bit]

    def max_xor(self, x: int, bits: int = 31) -> int:
        node = self
        out = 0
        for b in range(bits, -1, -1):
            bit = (x >> b) & 1
            opposite = 1 - bit
            if node.children[opposite]:
                out |= 1 << b
                node = node.children[opposite]
            else:
                node = node.children[bit]
        return out

Bài tự luyện cuối chương

• LC 421, 1707, 1803, 1938, 2317.

---

41.1 Maximum XOR of Two Numbers (LC 421) - Trie version

Đã giải bằng “greedy bit + set” ở Chương 21.6. Trie cách thanh lịch hơn.

Đề bài

Cho nums. Trả về max XOR của 2 phần tử khác nhau.

Ví dụ

Input:  nums = [3, 10, 5, 25, 2, 8]
Output: 28   (max XOR giữa 2 phần tử bất kỳ: 5 XOR 25 = 28)

Ràng buộc

• 1 <= len(nums) <= 2·10^5
• 0 <= nums[i] <= 2^31-1

Clarifying questions

• Mảng có chứa số trùng? → Có; XOR vẫn đúng.
• Mảng < 2 phần tử? → Theo đề: ≥ 2.

Hướng tiếp cận

Build Trie binary của các số. Với mỗi x, query max_xor(x) (DFS theo bit ngược lại). Lấy max qua tất cả x.

Code Python 3

from typing import List

class _Trie:
    __slots__ = ("children",)
    def __init__(self):
        self.children = [None, None]


class Solution:
    BITS = 31

    def findMaximumXOR(self, nums: List[int]) -> int:
        root = _Trie()
        for x in nums:
            node = root
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                if not node.children[bit]:
                    node.children[bit] = _Trie()
                node = node.children[bit]

        best = 0
        for x in nums:
            node = root
            cur = 0
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                opp = 1 - bit
                if node.children[opp]:
                    cur |= 1 << b
                    node = node.children[opp]
                else:
                    node = node.children[bit]
            best = max(best, cur)
        return best

Phân tích độ phức tạp

• Thời gian: O(n · 32) = O(n).
• Bộ nhớ: O(n · 32) cho Trie.

Bình luận

• Trie nhị phân (Binary Trie) là cấu trúc dữ liệu tiêu biểu cho bài XOR; sẽ tái xuất ở 41.2–41.5.

Bài tự luyện liên quan

• LC 1707, 2935.

---

41.2 Maximum XOR With an Element From Array (LC 1707)

Đề bài

Cho nums và queries[i] = [x, m]. Với mỗi query, trả về max XOR giữa x và một số y ∈ nums với y ≤ m. Không có y → -1.

Ví dụ

Input:  nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3, 3, 7]

Ràng buộc

• 1 <= len(nums), len(queries) <= 10^5
• 0 <= nums[i], x_i, m_i <= 10^9

Clarifying questions

• query với m < min(nums)? → Không có y hợp lệ → trả -1.
• nums hoặc queries rỗng? → Theo đề: ≥ 1.

Hướng tiếp cận

Offline + sort + Trie.

• Sort queries theo m tăng.
• Sort nums tăng.
• Khi xử lý query, thêm các nums[i] ≤ m vào Trie rồi query max_xor(x).

Code Python 3

from typing import List

class _Trie:
    __slots__ = ("children",)
    def __init__(self):
        self.children = [None, None]


class Solution:
    BITS = 30  # nums, x ≤ 10^9 < 2^30

    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        def insert(root, x):
            node = root
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                if not node.children[bit]:
                    node.children[bit] = _Trie()
                node = node.children[bit]

        def max_xor(root, x):
            node = root
            out = 0
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                opp = 1 - bit
                if node.children[opp]:
                    out |= 1 << b
                    node = node.children[opp]
                else:
                    node = node.children[bit]
            return out

        nums.sort()
        indexed = sorted(enumerate(queries), key=lambda kv: kv[1][1])
        result = [-1] * len(queries)
        root = _Trie()
        i = 0
        for q_idx, (x, m) in indexed:
            while i < len(nums) and nums[i] <= m:
                insert(root, nums[i])
                i += 1
            if i == 0:
                result[q_idx] = -1
            else:
                result[q_idx] = max_xor(root, x)
        return result

Phân tích độ phức tạp

• Thời gian: O((n + q) · 30). Bộ nhớ: O(n · 30).

Bình luận

• Offline trick: sort queries trước → có thể tận dụng monotonic structure (Trie cũng vậy).

Bài tự luyện liên quan

• LC 1697 - Checking Existence of Edge Length Limited Paths.

---

41.3 Count Pairs With XOR in a Range (LC 1803)

Đề bài

Cho nums và [low, high]. Đếm số cặp (i, j) với i < j và low <= nums[i] ^ nums[j] <= high.

Ví dụ

Input:  nums = [1, 4, 2, 7], low = 2, high = 6
Output: 6

Giải thích 6 cặp (i, j) thoả 2 ≤ nums[i] ^ nums[j] ≤ 6:
  (0,1) 1 ^ 4 = 5      ✓
  (0,2) 1 ^ 2 = 3      ✓
  (0,3) 1 ^ 7 = 6      ✓
  (1,2) 4 ^ 2 = 6      ✓
  (1,3) 4 ^ 7 = 3      ✓
  (2,3) 2 ^ 7 = 5      ✓

Ràng buộc

• 1 <= len(nums) <= 2·10^4
• 1 <= nums[i] <= 2·10^4
• 1 <= low <= high <= 2·10^4

Clarifying questions

• low > high? → Theo đề: low <= high.
• Mảng có giá trị âm? → Theo đề: 1 <= nums[i] <= 2·10^4.

Hướng tiếp cận

count_xor_less(x) = số cặp (num, y) (y đã insert trước) có num ^ y < x. Đáp án = count_xor_less(high + 1) - count_xor_less(low).

Trie có thêm count ở mỗi node = số y đã đi qua node đó. Với mỗi num, đi từ bit cao xuống thấp; tại bit hiện hành gọi bit_n = bit của num, bit_x = bit của x:

• Nếu bit_x = 1: XOR ở bit này có thể là 0 hoặc 1 mà vẫn < x ở prefix này. Nếu XOR bit = 0 (tức y có cùng bit với num, đi qua children[bit_n]) thì các bit dưới tự do ⇒ cộng nguyên cả subtree: total += node.children[bit_n].count. Sau đó “deserve” XOR bit = 1 bằng cách đi xuống nhánh children[1 - bit_n] (opposite) để xét tiếp các bit thấp.
• Nếu bit_x = 0: XOR bit này bắt buộc = 0 (nếu = 1 sẽ ≥ x ở prefix). Đi xuống nhánh children[bit_n] (cùng bit num), không cộng gì.

Nói gọn: “same bit ⇒ XOR = 0” và “opposite bit ⇒ XOR = 1”. Code dưới đếm subtree same (XOR = 0) khi bit_x = 1, rồi chuyển con trỏ sang opposite để tiếp tục.

Code Python 3

from typing import List

class _TrieCnt:
    __slots__ = ("children", "count")
    def __init__(self):
        self.children = [None, None]
        self.count = 0


class Solution:
    BITS = 15  # nums[i] ≤ 2·10^4 < 2^15

    def countPairs(self, nums: List[int], low: int, high: int) -> int:

        def count_less(target: int) -> int:
            root = _TrieCnt()
            total = 0
            for num in nums:
                node = root
                for b in range(self.BITS, -1, -1):
                    bit_n = (num >> b) & 1
                    bit_x = (target >> b) & 1
                    if bit_x == 1:
                        # XOR bit = 0 (cùng bit) → subtree cùng nhánh đếm hết.
                        if node.children[bit_n]:
                            total += node.children[bit_n].count
                        # Đi xuống nhánh XOR bit = 1 (= opposite).
                        if node.children[1 - bit_n]:
                            node = node.children[1 - bit_n]
                        else:
                            node = None
                            break
                    else:
                        # Bắt buộc XOR bit = 0 → đi xuống cùng nhánh.
                        if node.children[bit_n]:
                            node = node.children[bit_n]
                        else:
                            node = None
                            break
                # Insert num vào Trie sau khi đếm.
                node = root
                for b in range(self.BITS, -1, -1):
                    bit_n = (num >> b) & 1
                    if not node.children[bit_n]:
                        node.children[bit_n] = _TrieCnt()
                    node = node.children[bit_n]
                    node.count += 1
            return total

        return count_less(high + 1) - count_less(low)

Phân tích độ phức tạp

• Thời gian: O(n · 15). Bộ nhớ: O(n · 15).

Bình luận

• Pattern “count less than” áp được cho mọi bài “count XOR in range” - đẹp.
• Bẫy: đếm bằng low <= ... <= high trực tiếp khó; tách thành < (high+1) và < low rồi trừ.

Bài tự luyện liên quan

• LC 421, 1707.

---

41.4 Maximum Genetic Difference Query (LC 1938)

Đề bài

Tree với parents[i] (cha của i, -1 cho root). Mỗi node trong LC này không có giá trị riêng - “giá trị” của node = chính chỉ số node. Mỗi query (node, val): tìm max val ^ x với x là chỉ số của một ancestor (kể cả node chính nó). Trả mảng max theo thứ tự query.

Ví dụ

Input:  parents = [-1, 0, 1, 1]
        queries = [[0, 2], [3, 2], [2, 5]]

        Cây thực tế (parents[0] = -1 nên 0 là root):
              0
              |
              1
             / \
            2   3

Output: [2, 3, 7]

Giải thích:
  query (0, 2): ancestor của 0 là {0};      max(2^0) = 2.
  query (3, 2): ancestor của 3 là {3,1,0};  max(2^3, 2^1, 2^0) = max(1,3,2) = 3.
  query (2, 5): ancestor của 2 là {2,1,0};  max(5^2, 5^1, 5^0) = max(7,4,5) = 7.

Ràng buộc

• 2 <= len(parents) <= 10^5
• 1 <= len(queries) <= 3·10^4
• 0 <= val_i <= 2·10^5

Clarifying questions

• Tree rỗng? → Không (theo đề n ≥ 1).
• Query có node = root? → val ^ root_index (chỉ số root) là một ứng viên.
• Giá trị node là gì? → Chính chỉ số node (không có mảng vals[] đi kèm).

Hướng tiếp cận

Offline DFS trên tree. Maintain Trie chứa chỉ số các ancestors của node hiện tại trên DFS path (bao gồm node chính nó).

• Khi DFS vào u: insert chỉ số u vào Trie, xử lý tất cả query gắn với u.
• Khi DFS ra u: xoá chỉ số u khỏi Trie.

Trie cần hỗ trợ remove - track count mỗi node để biết khi nào prune nhánh khi count về 0.

Code Python 3

import sys
from collections import defaultdict
from typing import List

class _TrieX:
    __slots__ = ("children", "count")
    def __init__(self):
        self.children = [None, None]
        self.count = 0


class Solution:
    BITS = 17  # node indices ≤ n - 1 ≤ 10^5 - 1 < 2^17

    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        sys.setrecursionlimit(10**6)
        n = len(parents)
        children = defaultdict(list)
        root_node = -1
        for v, p in enumerate(parents):
            if p == -1:
                root_node = v
            else:
                children[p].append(v)

        # Group queries by node.
        node_queries = defaultdict(list)
        for q_idx, (node, val) in enumerate(queries):
            node_queries[node].append((q_idx, val))

        root = _TrieX()
        result = [0] * len(queries)

        def insert(x: int) -> None:
            node = root
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                if not node.children[bit]:
                    node.children[bit] = _TrieX()
                node = node.children[bit]
                node.count += 1

        def remove(x: int) -> None:
            node = root
            path = []
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                path.append((node, bit))
                node = node.children[bit]
                node.count -= 1
            # Prune branches with count = 0.
            for parent, bit in reversed(path):
                if parent.children[bit] and parent.children[bit].count == 0:
                    parent.children[bit] = None

        def query_max(val: int) -> int:
            node = root
            out = 0
            for b in range(self.BITS, -1, -1):
                bit = (val >> b) & 1
                opp = 1 - bit
                if node.children[opp] and node.children[opp].count > 0:
                    out |= 1 << b
                    node = node.children[opp]
                else:
                    node = node.children[bit]
            return out

        def dfs(u: int) -> None:
            insert(u)
            for q_idx, val in node_queries[u]:
                result[q_idx] = query_max(val)
            for v in children[u]:
                dfs(v)
            remove(u)

        dfs(root_node)
        return result

Phân tích độ phức tạp

• Thời gian: O((n + q) · 17). Bộ nhớ: O(n · 17).

Bình luận

• Đây là bài Hard; ý chính là DFS trên cây kết hợp Trie có hỗ trợ remove (xoá khi DFS quay lui). Pattern này hay gặp ở các bài tree XOR query.
• Bẫy: với tree lớn (n = 10^5), DFS đệ quy có thể stack overflow → chuyển sang iterative.

Bài tự luyện liên quan

• LC 421, 1707.

---

41.5 Maximum Strong Pair XOR II (LC 2935)

Đề bài

Cặp (x, y) “strong” ↔︎ |x - y| <= min(x, y). Cho nums. Tìm max XOR trong các cặp strong.

Ví dụ

Input:  nums = [1, 2, 3, 4, 5]
Output: 7   (cặp "strong" là (x, y) với |x - y| ≤ min(x, y); max XOR = 3 XOR 4 = 7)

Ràng buộc

• 1 <= len(nums) <= 5·10^4
• 1 <= nums[i] <= 2^20

Clarifying questions

• Mảng có cùng giá trị? → Có; cùng giá trị tạo strong pair (|x-y| = 0 ≤ min).

Hướng tiếp cận

Quan sát: |x - y| ≤ min(x, y) ↔︎ max(x, y) ≤ 2 · min(x, y) (giả sử both ≥ 0). Sort nums, sliding window: với mỗi r, mở rộng l đến khi nums[r] > 2 · nums[l].

Trong window [l, r], max XOR = query Trie. Sliding Trie: khi l tiến, remove nums[l]. Khi r mới, insert nums[r].

Code Python 3

from typing import List

class _TrieRem:
    __slots__ = ("children", "count")
    def __init__(self):
        self.children = [None, None]
        self.count = 0


class Solution:
    BITS = 20  # nums ≤ 2·10^5 < 2^20

    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        root = _TrieRem()

        def insert(x: int) -> None:
            node = root
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                if not node.children[bit]:
                    node.children[bit] = _TrieRem()
                node = node.children[bit]
                node.count += 1

        def remove(x: int) -> None:
            node = root
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                node = node.children[bit]
                node.count -= 1

        def query_max(x: int) -> int:
            node = root
            out = 0
            for b in range(self.BITS, -1, -1):
                bit = (x >> b) & 1
                opp = 1 - bit
                if node.children[opp] and node.children[opp].count > 0:
                    out |= 1 << b
                    node = node.children[opp]
                else:
                    node = node.children[bit]
            return out

        l = 0
        best = 0
        for r in range(len(nums)):
            insert(nums[r])
            while nums[r] > 2 * nums[l]:
                remove(nums[l])
                l += 1
            best = max(best, query_max(nums[r]))
        return best

Phân tích độ phức tạp

• Thời gian: O(n · 20 + n log n). Bộ nhớ: O(n · 20).

Bình luận

• Sliding window + Trie với remove - pattern xuất hiện ở các bài XOR với range constraint.

Bài tự luyện liên quan

• LC 421, 1938.

---

41.6 Maximum XOR After Operations (LC 2317)

Đề bài

Cho nums. Op: chọn nums[i] và bất kỳ x ≥ 0, đặt nums[i] = nums[i] AND (nums[i] XOR x). Tìm max XOR all elements sau ops bất kỳ.

Ví dụ

Input:  nums = [3, 2, 4, 6]
Output: 7   (mỗi phép: chọn i, x; thay nums[i] = nums[i] AND (nums[i] XOR x);
             max XOR toàn mảng đạt được = OR mọi nums[i] = 3|2|4|6 = 7)

Ràng buộc

• 1 <= len(nums) <= 10^5
• 0 <= nums[i] <= 10^9

Clarifying questions

• All zeros? → Trả 0.
• n = 1? → Trả nums[0].

Hướng tiếp cận

Insight: Op cho phép tắt bit bất kỳ của nums[i] (giữ bit có sẵn). Vì XOR all = OR all khi mỗi bit có thể “toggle tự do” từ ít nhất 1 số → max = OR all.

Code Python 3

from typing import List

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        result = 0
        for x in nums:
            result |= x
        return result

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

• Bài “1 dòng nếu hiểu” - tinh tuý của bit manipulation.
• Bài này không cần Trie - chỉ insight đại số. Đặt vào chương vì nằm trong syllabus gốc và là bài XOR.

Bài tự luyện liên quan

• LC 421, 2895.

Tóm tắt chương & Quyết định

Tên chương - “Binary Trie for XOR”

Tên đầy đủ hơn: Binary Trie để tối ưu XOR/operation theo từng bit. “Bitmask kết hợp Trie” trong index folder chỉ là viết tắt.

Count Pairs With XOR in Range (LC 1803) - bit-level

• count(L, R) = count(≤ R) - count(≤ L - 1). Build hàm countLE(limit).
• countLE(limit) với mỗi a[i]: đi từ bit cao xuống thấp.
  • Tại bit b, nếu bit của limit là 1:
    • Đếm các số đã insert có XOR bit b với a[i] = 0 (tức cùng bit với a[i]) → chắc chắn ≤ limit ở bit này, cộng số đó vào answer.
    • Đi tiếp xuống bit thấp với nhánh “khác bit a[i]”.
  • Nếu bit limit là 0: chỉ đi nhánh “cùng bit a[i]”.

Genetic Difference (LC 1938) - node value = node index

LC này dùng parents[i] để build cây; value của node i đơn giản là i. Trie chứa giá trị i dọc đường từ root → query.

Strong Pair (LC 2941) - derivation

• “Strong” định nghĩa |x - y| ≤ min(x, y). Giả sử x ≤ y ⇒ y - x ≤ x ⇒ y ≤ 2x.
• Sort tăng dần ⇒ với mỗi y, các candidate x thoả x ≥ y/2 nằm trong suffix đã thêm. Maintain sliding window trên trie.

---