From my experience as a CodeChef Problem Setter, mastering advanced data structures is crucial for solving complex problems efficiently. Here's a deep dive into essential structures every competitive programmer should know.

1. Segment Trees with Lazy Propagation

For range queries and updates in O(log n):

// Segment Tree with Lazy Propagation
class SegmentTree {
    vector<int> tree, lazy;
    int n;
    
    void build(int node, int start, int end, vector<int>& arr) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(2*node, start, mid, arr);
        build(2*node+1, mid+1, end, arr);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    
    void updateRange(int node, int start, int end, int l, int r, int val) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
        
        if (start > end || start > r || end < l) return;
        
        if (start >= l && end <= r) {
            tree[node] += (end - start + 1) * val;
            if (start != end) {
                lazy[2*node] += val;
                lazy[2*node+1] += val;
            }
            return;
        }
        
        int mid = (start + end) / 2;
        updateRange(2*node, start, mid, l, r, val);
        updateRange(2*node+1, mid+1, end, l, r, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    
    int queryRange(int node, int start, int end, int l, int r) {
        if (start > end || start > r || end < l) return 0;
        
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
        
        if (start >= l && end <= r) return tree[node];
        
        int mid = (start + end) / 2;
        int left = queryRange(2*node, start, mid, l, r);
        int right = queryRange(2*node+1, mid+1, end, l, r);
        return left + right;
    }
public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4*n);
        lazy.resize(4*n, 0);
        build(1, 0, n-1, arr);
    }
};

Applications:

2. Fenwick Tree (Binary Indexed Tree)

More efficient than Segment Tree for prefix sum queries:

// Fenwick Tree Implementation
class FenwickTree {
    vector<int> bit;
    int n;
    
    int sum(int idx) {
        int ret = 0;
        for (; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }
    
public:
    FenwickTree(int size) {
        n = size;
        bit.assign(n + 1, 0);
    }
    
    FenwickTree(vector<int>& arr) : FenwickTree(arr.size()) {
        for (int i = 0; i < n; i++)
            add(i, arr[i]);
    }
    
    void add(int idx, int delta) {
        for (++idx; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }
    
    int range_sum(int l, int r) {
        return sum(r + 1) - sum(l);
    }
    
    // Lower bound: smallest idx such that prefix sum >= val
    int lower_bound(int val) {
        int pos = 0, sum = 0;
        for (int i = 20; i >= 0; i--) {
            int next = pos + (1 << i);
            if (next <= n && sum + bit[next] < val) {
                sum += bit[next];
                pos = next;
            }
        }
        return pos;
    }
};

When to Use:

Use Fenwick Tree When Use Segment Tree When
Only need prefix/range sum queries Need complex range operations
Memory is constrained Need range min/max with updates
Need O(1) point updates Need lazy propagation
Implementing order statistics Need to merge nodes in custom ways

3. Advanced Trie Implementations

Beyond basic prefix matching - my Auto Complete project extensions:

// Compressed Trie (Radix Tree)
class CompressedTrieNode {
    unordered_map<string, CompressedTrieNode*> children;
    bool isEnd;
    vector<string> suggestions;
    
public:
    CompressedTrieNode() : isEnd(false) {}
    
    void insert(const string& word) {
        insertUtil(word, 0);
    }
    
    vector<string> autocomplete(const string& prefix) {
        return autocompleteUtil(prefix, 0);
    }
};

// Trie for XOR operations (XOR Trie)
class XorTrie {
    struct Node {
        Node* children[2];
        Node() {
            children[0] = children[1] = nullptr;
        }
    };
    
    Node* root;
    
public:
    XorTrie() {
        root = new Node();
    }
    
    void insert(int num) {
        Node* curr = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!curr->children[bit])
                curr->children[bit] = new Node();
            curr = curr->children[bit];
        }
    }
    
    int maxXor(int num) {
        Node* curr = root;
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int desired = 1 - bit;
            
            if (curr->children[desired]) {
                result |= (1 << i);
                curr = curr->children[desired];
            } else {
                curr = curr->children[bit];
            }
        }
        return result;
    }
};

4. Disjoint Set Union (Union-Find) with Optimizations

// DSU with path compression and union by rank
class DSU {
    vector<int> parent, rank, size;
    
public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return;
        
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
            rank[rootX]++;
        }
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    int componentSize(int x) {
        return size[find(x)];
    }
    
    // For dynamic connectivity problems
    void rollback() {
        // Implementation for persistent DSU
    }
};

5. Sparse Table for RMQ

For Range Minimum Queries with O(1) query and O(n log n) preprocessing:

// Sparse Table for RMQ (Range Minimum Query)
class SparseTable {
    vector<vector<int>> st;
    vector<int> log;
    
    int operation(int a, int b) {
        return min(a, b); // Can be max, gcd, etc.
    }
    
public:
    SparseTable(vector<int>& arr) {
        int n = arr.size();
        int k = log2(n) + 1;
        
        st.resize(n, vector<int>(k));
        log.resize(n + 1);
        
        // Precompute logs
        log[1] = 0;
        for (int i = 2; i <= n; i++)
            log[i] = log[i/2] + 1;
        
        // Build sparse table
        for (int i = 0; i < n; i++)
            st[i][0] = arr[i];
        
        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = operation(
                    st[i][j-1],
                    st[i + (1 << (j-1))][j-1]
                );
            }
        }
    }
    
    int query(int l, int r) {
        int j = log[r - l + 1];
        return operation(
            st[l][j],
            st[r - (1 << j) + 1][j]
        );
    }
};

Problem-Solving Patterns

Sliding Window + Deque

For problems like "Maximum in all subarrays of size k":

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        // Remove indices outside window
        if (!dq.empty() && dq.front() == i - k)
            dq.pop_front();
        
        // Maintain decreasing order
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();
        
        dq.push_back(i);
        
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

Mo's Algorithm

For offline range queries in O((n+q)√n):

struct Query {
    int l, r, idx;
    bool operator<(Query other) const {
        if (l / block != other.l / block)
            return l < other.l;
        return (l / block & 1) ? (r < other.r) : (r > other.r);
    }
};

Complexity Analysis Table

Data Structure Build Time Query Time Update Time Space Best For
Segment Tree O(n) O(log n) O(log n) O(4n) Range updates/queries
Fenwick Tree O(n) O(log n) O(log n) O(n) Prefix sum, point updates
Sparse Table O(n log n) O(1) Not supported O(n log n) Static RMQ
Trie O(L) O(L) O(L) O(26^L) String prefix search

Pro Tip: During CodeChef problem setting, we often create problems that require combining multiple data structures. Practice identifying which structure to use based on operation requirements rather than memorizing implementations.

Practice Problems