Policy-Based Data Structures (PBDS) in Competitive Programming

By
Mohammad Fatin Nur
-
2
153

In competitive programming, efficiency and correctness are paramount, and selecting the appropriate data structure can significantly impact performance. One such versatile and powerful data structure is the policy-based data structure, which is part of the GNU C++ library extension. This extension provides features that can greatly simplify and optimize certain operations.

Setting Up PBDS

1. Include the Necessary Headers:

    PBDS is part of the GNU C++ library extension, so you need to include the following headers:

    #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

    2. Add Namespace:

    PBDS functions reside in the __gnu_pbds namespace, so you can use:

    using namespace __gnu_pbds;

    3. Defining the PBDS templete:

    For most competitive programming problems, you will find the ordered set with order statistics most useful. Here’s how to define and use it:

    template<typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

    The less<T> comparator will give you an ordered set. Use the less_equal<T> comparator to get an ordered multiset.

    Here is a PBDS template:

    #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using pbds = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

    Operations

    Just like set and multiset, you can perform insert, erase, and find operations. Additionally, you can perform two cool operations:

    Order of Key

    order_of_key returns the number of elements in the set that are strictly less than the given value. If you want to count elements that are less than or equal to a given value, you can use order_of_key with the next integer value. The time complexity is O(log(n)).

    Find by Order

    find_by_order returns an iterator to the k-th smallest element in the set (0-based index). The time complexity is O(log(n)).

    #include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<typename T>using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
    pbds<int> pb;
    pb.insert(10);
    pb.insert(20);
    pb.insert(15);
    pb.insert(30);

    // Find the number of elements strictly less than 15
    cout<<"Number of elements less than 15: "<<pb.order_of_key(15)<<endl; // Output: 2

    // Find the number of elements less than or equal to 15
    cout<<"Number of elements less than or equal to 5: "<<pb.order_of_key(16)<<endl; // Output: 3

    // Find the k-th smallest element (0-based index)
    auto it = pb.find_by_order(1);
    if(it!=pb.end()){
        cout<<"The 2nd smallest element is: "<<*it<<endl; // Output: 10
    }
}

    When to Use Policy-Based Data Structures

    1. Dynamic Queries and Updates: Problems where the data is constantly changing and you need efficient access to order statistics or ranked elements.
    2. Complex Set Operations: Problems requiring advanced operations like finding the k-th smallest element, counting elements within a range, or maintaining a dynamic list of elements.
    3. Optimization Problems: Scenarios where brute force or simpler data structures like set or map would be too slow or cumbersome

    Conclusion

    Policy-based data structures in the GNU C++ library provide powerful tools that extend the capabilities of standard containers like sets and maps. Their ability to perform advanced operations in logarithmic time makes them invaluable in competitive programming, where efficiency can be the difference between winning and losing. Understanding and utilizing these data structures can give competitors a significant edge in tackling a wide range of algorithmic problems.

    Practice Problems

    2 COMMENTS