Competitive Programming Library

Test

g++ ./tests/main.cpp -std=c++17 -o temp && ./temp && rm ./temp

Data Structures

Disjoint Set: Union by Rank

Initialization:

• Time Complexity: O(N)
• Space Complexity: O(N)

 DisjointSet dsu(size);

Operations

Find Set Representative

• Avg. Time Complexity: O(1)
• Time Complexity: O(log N)
• Space Complexity: O(1)

dsu.find_set(int i);

Merge Set

• Avg. Time Complexity: O(1)
• Time Complexity: O(log N)
• Space Complexity: O(1)

dsu.merge_set(int i, int j)

Check If Same Set

• Avg. Time Complexity: O(1)
• Time Complexity: O(log N)
• Space Complexity: O(1)

dsu.is_same_set(int i, int j)

Segment Tree

Initialization:

• Time Complexity: O(N)
• Space Complexity: O(N)

SegmentTree<int> segment_tree(arr, 0, [&](int a, int b) {
    return a+b;
});

Operations

Point Update

• Time Complexity: O(log N)
• Space Complexity: O(1)

segment_tree.update(i, value);

Range Query

• Time Complexity: O(log N)
• Space Complexity: O(log N)

segment_tree.get(i, j)

Static Hash

Examples:

1. StaticHash hash;
2. StaticHash hash(31);
3. StaticHash hash(31, 'a');
4. StaticHash hash(31, 'a', 1e9+9);

Rolling Hash

Examples:

1. RollingHash hash;
2. RollingHash hash(31);
3. RollingHash hash(31, 'a');
4. RollingHash hash(31, 'a', 1e9+9);

Custom Stack

Usage

Can be used to build min/max/sum/xor Stack using any appropriate associative function

Initialization:

// Max Stack
CustomStack<int> st(0, [&](int a, int b) {
    return std::max(a, b);
});

Operations:

1. st.custom_value()
2. st.empty()
3. st.push(value)
4. st.pop()
5. st.size()
6. st.top()

Custom Queue

Usage

Can be used to build min/max/sum/xor Queue using any appropriate associative function

Initialization:

// Max Queue
CustomQueue<int> qu(0, [&](int a, int b) {
    return std::max(a, b);
});

Operations:

1. qu.custom_value()
2. qu.empty()
3. qu.front()
4. qu.push(value)
5. qu.pop()
6. qu.size()