Data Structures & Algorithms

The Fenwick Tree (invented by Peter Fenwick in 1994) is one of the most compact data structures ever devised. It gives you the full power of a dynamic segment tree in just one flat array of size N with 10 lines of code.

1. The Secret: Powers of 2 Range Decomposition

Any positive integer can be uniquely represented as a sum of powers of 2. For example: 13 = 8 + 4 + 1.

Fenwick took this idea and applied it to prefix ranges: instead of storing every single element, tree[i] stores the sum of a contiguous range of length equal to its lowest set bit!

The length of the range responsible by index i is given by: lowbit(i) = i & (-i).

• If i = 12 (1100_2): lowbit(12) = 4. So tree[12] stores the sum of 4 elements: indices [9, 10, 11, 12]!
• If i = 8 (1000_2): lowbit(8) = 8. So tree[8] stores the sum of the first 8 elements: [1 ... 8]!

2. The Two Operations

A. Prefix Sum Query: `i -= (i & -i)`

To calculate the prefix sum up to index 13:

1. Read tree[13] (covers index 13). 13 - lowbit(13) = 13 - 1 = 12.
2. Read tree[12] (covers indices 9 through 12). 12 - lowbit(12) = 12 - 4 = 8.
3. Read tree[8] (covers indices 1 through 8). 8 - lowbit(8) = 8 - 8 = 0 (Done!).

Total reads: only 3 steps to sum 13 numbers! At each step, you strip off one binary bit, taking at most O(log N) operations.

B. Point Update: `i += (i & -i)`

When you add delta to element i, which parent ranges need to be updated? Every index whose range covers i! You navigate up the tree simply by adding the lowest set bit: i += (i & -i)!

Clean C++20 Implementation

#include <vector>
#include <cstdint>

class FenwickTree {
    std::vector<int64_t> tree;
    int n;

    static inline int lowbit(int x) {
        return x & (-x);
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // Adds delta to index i (1-indexed) in O(log N)
    void update(int i, int64_t delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    // Computes sum of prefix [1 ... i] in O(log N)
    int64_t query(int i) const {
        int64_t sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    // Computes range sum [l ... r] in O(log N)
    int64_t queryRange(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

Why Fenwick Beats Segment Trees in Production

Floyd’s cycle algorithm is pure mathematical poetry. Let’s write out the distances with simple algebra so the proof is crystal clear.

1. Defining the Variables

Let’s map out the linked list into three distinct segments:

• L: Distance from the head to the cycle entrance.
• C: Total length (circumference) of the cycle.
• x: Distance from the cycle entrance to the meeting point inside the cycle.

2. Distance Traveled by Each Pointer

When the Tortoise (slow) and Hare (fast) meet:

• Slow moved: Dist_slow = L + x
• Fast moved: Dist_fast = L + n * C + x (where n is how many full laps fast ran around the cycle).

Because the fast pointer moves at twice the speed of slow:

Dist_fast = 2 * Dist_slow
L + n * C + x = 2 * (L + x)
L + n * C + x = 2L + 2x

Now subtract L + x from both sides:

n * C = L + x
L = n * C - x
L = (n - 1) * C + (C - x)

3. What does L = (n – 1) * C + (C – x) mean?

Look carefully at that equation:

• L is the distance from head to the cycle entrance.
• (C - x) is the distance from the meeting point to the cycle entrance!
• (n - 1) * C is just zero or more full loops around the cycle!

Conclusion: If you place Pointer 1 at head (which must travel distance L) and Pointer 2 at meeting_point (which travels distance (C - x) plus some optional full laps), both pointers will meet at the EXACT same node: the cycle entrance!

Clean Python 3.12 Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detect_cycle_entry(head: ListNode | None) -> ListNode | None:
    """Finds the node where cycle begins in O(N) time and O(1) space."""
    if not head or not head.next:
        return None

    slow = head
    fast = head

    # Phase 1: Determine if a cycle exists
    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    # Phase 2: Find cycle entrance
    ptr1 = head
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

Complexity Breakdown

• Time Complexity: O(N). Phase 1 takes at most $2N$ steps. Phase 2 takes at most $N$ steps.
• Space Complexity: O(1). No hash set or memory allocation.

The Maximum XOR problem is the ultimate showcase of how bit manipulation and trees blend together. Once you see the greedy nature of binary numbers, the Binary Trie solution becomes second nature.

1. The Greedy Bit Principle

In binary numbers, the Most Significant Bit (MSB) has more numerical value than all lower bits combined! For example, bit 30 ($2^{30} pprox 1.07 imes 10^9$) is strictly greater than the sum of all bits from 0 to 29 combined ($2^{30} – 1$).

Therefore, to maximize an XOR sum, you must be greedy from left to right (MSB down to LSB):

• If the current bit of number num is 1, you desperately want to pair it with a number whose corresponding bit is 0 (because 1 ^ 0 = 1).
• If the current bit of num is 0, you want to pair it with a number whose corresponding bit is 1 (because 0 ^ 1 = 1).

2. Why a Binary Trie?

A Binary Trie is just a tree where every node has at most two children: 0 (left) and 1 (right).

1. Insert: You insert each number into the Trie as a 31-bit or 32-bit string of binary digits, from bit 31 down to bit 0.
2. Query: For each number x, you walk down the Trie. At each bit b, you ask: ‘Does the opposite branch (1 - b) exist?’
   • If YES: Take that branch! That bit in your XOR result becomes 1.
   • If NO: You’re forced to take the same branch (b), so that bit in your XOR result becomes 0.

Because you made the best possible choice at every single bit position starting from the highest power of 2, the final accumulated number is mathematically guaranteed to be the global maximum XOR!

Clean Python 3.12 Implementation

class TrieNode:
    __slots__ = ('children',)
    def __init__(self):
        self.children: list[TrieNode | None] = [None, None]

class Solution:
    def find_maximum_xor(self, nums: list[int]) -> int:
        root = TrieNode()

        # Step 1: Insert all numbers into the 31-bit binary trie
        for num in nums:
            curr = root
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                if not curr.children[bit]:
                    curr.children[bit] = TrieNode()
                curr = curr.children[bit]

        # Step 2: Query each number against the trie
        max_xor = 0
        for num in nums:
            curr = root
            current_xor = 0
            for i in range(30, -1, -1):
                bit = (num >> i) & 1
                opposite_bit = 1 - bit
                
                # Greedily check if the complementary bit exists
                if curr.children[opposite_bit]:
                    current_xor |= (1 << i)
                    curr = curr.children[opposite_bit]
                else:
                    curr = curr.children[bit]
                    
            max_xor = max(max_xor, current_xor)

        return max_xor

Complexity Breakdown

• Time Complexity: O(31 * N) = O(N). Inserting N numbers takes 31 * N operations. Querying N numbers takes 31 * N operations. Total time is strictly linear in the number of elements.
• Space Complexity: O(31 * N) worst-case node allocations. In practice, prefix branches overlap heavily, keeping memory around a few megabytes.