A classic strcuture for managing dynamic connectivity and equivalence classes.

Initialization

int parent[N];
void initUnionFind() {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
}

Path Compression Find

int findRoot(int x) {
    return parent[x] == x ? x : parent[x] = findRoot(parent[x]);
}

Union by Root

void unite(int a, int b) {
    int ra = findRoot(a), rb = findRoot(b);
    if (ra != rb) parent[rb] = ra;
}

Compact Version with std::iota

int uf[N];
void initUF() { std::iota(uf + 1, uf + n + 1, 1); }
int find(int x) { return uf[x] == x ? x : uf[x] = find(uf[x]); }
void join(int x, int y) { uf[find(y)] = find(x); }

Monotonic Deque (Sliding Window Minimum/Maximum)

Efficiently computes extremal values over fixed-size windows in O(n).

int dq[N], head = 1, tail = 0;
for (int i = 1; i <= n; ++i) {
    // Remove indices outside current window [i−k+1, i]
    while (head <= tail && dq[head] < i - k + 1) ++head;
    // Maintain monotonicity: pop larger elements from tail
    while (head <= tail && arr[dq[tail]] > arr[i]) --tail;
    dq[++tail] = i;
    if (i >= k) result[i - k + 1] = arr[dq[head]];
}

Monotonic Stack (Next Greater/Smaller Element)

Finds nearest greater element to the right in linear time.

int stack[N], top = 0;
int nextGreater[N]; // nextGreater[i] = index of first j>i where arr[j]>arr[i]
for (int i = n; i >= 1; --i) {
    while (top && arr[stack[top]] <= arr[i]) --top;
    nextGreater[i] = top ? stack[top] : 0;
    stack[++top] = i;
}

Doubly Linked List (Index-Based)

Lightweight, array-backed doubly linked list for O(1) insertions/deletions.

Node Structure

struct ListNode {
    int value;
    int next, prev;
} nodes[MAX_NODES];
int nodeCount = 0;

Initialization (Sentinel Head & Tail)

void initializeList() {
    nodes[0] = {0, n + 1, 0};      // head
    nodes[n + 1] = {0, n + 1, 0};  // tail
}

Insert After Position

void insertAfter(int pos, int val) {
    int newNode = ++nodeCount;
    nodes[newNode] = {val, nodes[pos].next, pos};
    nodes[nodes[pos].next].prev = newNode;
    nodes[pos].next = newNode;
}

Delete Node

void deleteNode(int pos) {
    nodes[nodes[pos].next].prev = nodes[pos].prev;
    nodes[nodes[pos].prev].next = nodes[pos].next;
}

ST Table (Sparse Table for RMQ)

Static Range Minimum/Maximum Query with O(1) per query and O(n log n) preprocessing.

int st[N][LOGN], logTable[N];

void buildST() {
    for (int i = 2; i <= n; ++i) {
        logTable[i] = logTable[i / 2] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        st[i][0] = arr[i];
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            st[i][j] = std::max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

int rangeMax(int l, int r) {
    int len = r - l + 1;
    int p = logTable[len];
    return std::max(st[l][p], st[r - (1 << p) + 1][p]);
}

Fenwick Tree (Binary Indexed Tree)

Efficient point-update and prefix-sum queries in O(log n).

int bit[N];

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

void update(int idx, int delta) {
    for (; idx <= n; idx += lowbit(idx)) {
        bit[idx] += delta;
    }
}

int prefixSum(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= lowbit(idx)) {
        sum += bit[idx];
    }
    return sum;
}

int rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

Segment Tree (Lazy Propagation)

Supports range updates and queries on arbitrary intervals.

struct SegNode {
    int left, right;
    long long sum, lazy;
    int length() const { return right - left + 1; }
};

SegNode tree[N * 4];

void pushDown(int p) {
    if (tree[p].lazy) {
        auto &cur = tree[p], &l = tree[p * 2], &r = tree[p * 2 + 1];
        l.sum += cur.lazy * l.length();
        r.sum += cur.lazy * r.length();
        l.lazy += cur.lazy;
        r.lazy += cur.lazy;
        cur.lazy = 0;
    }
}

void pullUp(int p) {
    tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}

void build(int l, int r, int p = 1) {
    tree[p] = {l, r, 0, 0};
    if (l == r) {
        tree[p].sum = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, p * 2);
    build(mid + 1, r, p * 2 + 1);
    pullUp(p);
}

void rangeAdd(int l, int r, long long val, int p = 1) {
    if (l <= tree[p].left && tree[p].right <= r) {
        tree[p].sum += val * tree[p].length();
        tree[p].lazy += val;
        return;
    }
    pushDown(p);
    int mid = (tree[p].left + tree[p].right) / 2;
    if (l <= mid) rangeAdd(l, r, val, p * 2);
    if (r > mid) rangeAdd(l, r, val, p * 2 + 1);
    pullUp(p);
}

long long rangeSum(int l, int r, int p = 1) {
    if (l <= tree[p].left && tree[p].right <= r) {
        return tree[p].sum;
    }
    pushDown(p);
    int mid = (tree[p].left + tree[p].right) / 2;
    long long res = 0;
    if (l <= mid) res += rangeSum(l, r, p * 2);
    if (r > mid) res += rangeSum(l, r, p * 2 + 1);
    return res;
}

Treap (Balenced BST)

Randomized binary search tree supporting insertion, deletion, rank, and selection.

Rotating Treap (Implicit Key)

struct TreapNode {
    int left, right;
    int key, priority;
    int count, size;
};

TreapNode nodes[MAX_TREAP];
int root = 0, nodeIdx = 0;

int newTreapNode(int key) {
    nodes[++nodeIdx] = {0, 0, key, rand(), 1, 1};
    return nodeIdx;
}

void updateSize(int p) {
    nodes[p].size = nodes[nodes[p].left].size +
                    nodes[nodes[p].right].size +
                    nodes[p].count;
}

void rotateRight(int &p) {
    int q = nodes[p].left;
    nodes[p].left = nodes[q].right;
    nodes[q].right = p;
    p = q;
    updateSize(nodes[p].right);
    updateSize(p);
}

void rotateLeft(int &p) {
    int q = nodes[p].right;
    nodes[p].right = nodes[q].left;
    nodes[q].left = p;
    p = q;
    updateSize(nodes[p].left);
    updateSize(p);
}

void insert(int key, int &p) {
    if (!p) {
        p = newTreapNode(key);
        return;
    }
    if (key == nodes[p].key) {
        ++nodes[p].count;
    } else if (key < nodes[p].key) {
        insert(key, nodes[p].left);
        if (nodes[nodes[p].left].priority > nodes[p].priority) {
            rotateRight(p);
        }
    } else {
        insert(key, nodes[p].right);
        if (nodes[nodes[p].right].priority > nodes[p].priority) {
            rotateLeft(p);
        }
    }
    updateSize(p);
}

FHQ Treap (Split-Merge Style)

int split(int p, int key, int &L, int &R) {
    if (!p) { L = R = 0; return 0; }
    if (nodes[p].key <= key) {
        L = p;
        split(nodes[p].right, key, nodes[p].right, R);
        updateSize(L);
    } else {
        R = p;
        split(nodes[p].left, key, L, nodes[p].left);
        updateSize(R);
    }
}

int merge(int L, int R) {
    if (!L || !R) return L | R;
    if (nodes[L].priority > nodes[R].priority) {
        nodes[L].right = merge(nodes[L].right, R);
        updateSize(L);
        return L;
    } else {
        nodes[R].left = merge(L, nodes[R].left);
        updateSize(R);
        return R;
    }
}

void insertFHQ(int key) {
    int L, R;
    split(root, key - 1, L, R);
    root = merge(L, merge(newTreapNode(key), R));
}

Cartesian Tree

Linear-time construction of a min-heap-ordered BST from an array.

int stack[N], top = 0;
int leftChild[N], rightChild[N];

for (int i = 1; i <= n; ++i) {
    int last = 0;
    while (top && arr[stack[top]] > arr[i]) {
        last = stack[top--];
    }
    if (top) rightChild[stack[top]] = i;
    leftChild[i] = last;
    stack[++top] = i;
}

Linear Basis (XOR Space)

Represents the XOR span of a set of integers using a minimal basis.

struct LinearBasis {
    long long base[64];
    LinearBasis() { std::fill(base, base + 64, 0LL); }

    void insert(long long x) {
        for (int i = 63; i >= 0; --i) {
            if ((x >> i) & 1) {
                if (!base[i]) {
                    base[i] = x;
                    break;
                }
                x ^= base[i];
            }
        }
    }

    long long maximumXOR() {
        long long res = 0;
        for (int i = 63; i >= 0; --i) {
            if ((res ^ base[i]) > res) {
                res ^= base[i];
            }
        }
        return res;
    }
};