|

I_Love_HoangTrang | Logout

HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP

ADAMANT BLOG TEAMS SUBMISSIONS GROUPS CONTESTS PROBLEMSETTING

adamant's blog → Pay attention

Before contest
C++ STL: Policy based data structures Codeforces Round (Div. 2)
6 days
By adamant, 11 years ago, translation,

Hi everyone! After a relatively long lull, I decided that my contribution growing too slowly the hour has come → I_Love_HoangTrang
to please you with another article in the blog :)
Rating: 1165
Contribution: 0
2 months ago user Perlik wrote an article, in which he described a very interesting STL implemented data
structure that allows you to quickly perform various operations with substrings. Some time after I tested it Settings
Blog
on various tasks and, unfortunately, tend to get a negative result — rope was too slow, especially when it Favourites I_Love_HoangTrang
came to working with individual elements. Teams
Submissions
Problemsetting
For some time, I forgot about that article. Increasingly, however, I was faced with problems in which it was Groups
necessary to implement set with the ability to know ordinal number of item and also to get item by its Talks
ordinal number (ie, order statistic in the set). And then I remembered that in the comments to that article, Contests
someone mentioned about the mysterious data structure order statistics tree, which supports these two
operations and which is implemented in STL (unfortunately only for the GNU C++). And here begins my
fascinating acquaintance with policy based data structures, and I want to tell you about them :) → Top rated

# User Rating
Let's get started. In this article I will talk about IMO the most interesting of the implemented structures — 1 tourist 3843
tree. We need to include the following headers: 2 jiangly 3700

3 orzdevinwang 3696
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update 4 jqdai0815 3682

5 Radewoosh 3631
After closer inspection you may find that the last two files contained in the library 6 maroonrk 3582

7 Ormlis 3556
#include <ext/pb_ds/detail/standard_policies.hpp>
8 Benq 3527

Namespace, which we will have to work in newer versions of C++ is called __gnu_pbds; , earlier it was 9 ksun48 3492
called pb_ds; 10 maspy 3489
Countries | Cities | Organizations View all →
Now let's look at the concrete structure.

The tree-based container has the following declaration: → Top contributors

# User Contrib.
template<
1 cry 162
typename Key, // Key type
typename Mapped, // Mapped-policy 2 Dominater069 159
typename Cmp_Fn = std::less<Key>, // Key comparison functor 3 Qingyu 158
typename Tag = rb_tree_tag, // Specifies which underlying data structure
3 -is-this-fft- 158
to use
5 atcoder_official 156
template<
typename Const_Node_Iterator, 6 djm03178 154

typename Node_Iterator, 7 errorgorn 153

typename Cmp_Fn_, 8 adamant 152
typename Allocator_>
9 luogu_official 151
class Node_Update = null_node_update, // A policy for updating node
10 soullless 143
invariants
typename Allocator = std::allocator<char> > // An allocator type View all →

class tree;
→ Find user

Experienced participants may have already noticed that if initialize the template only the first two types, we Handle:
obtain almost exact copy of the container map . Just say, that this container can be set , for this you
just need to specify the second argument template type as null_type ( in older versions it is Find

null_mapped_type ).

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 1 / 19
:
 By the way Tag and Node_Update are missing in map . Let us examine them in more detail. → Recent actions

Tag — class denoting a tree structure, which we will use. There are three base-classes provided in STL sweetweasel → How was round 1024 ?
for this, it is rb_tree_tag (red-black tree), splay_tree_tag (splay tree) and ov_tree_tag
i_m_abbhay → Help My 14-Year-Old Brother
(ordered-vector tree). Sadly, at competitions we can use only red-black trees for this because splay tree and Love Competitive Programming!
OV-tree using linear-timed split operation that prevents us to use them.
Square__Head → A lot of new problems
were added to cses
Node_Update — class denoting policy for updating node invariants. By default it is set to
Shoo → Codeforces Round 1024 (Div. 1,
null_node_update , ie, additional information not stored in the vertices. In addition, C++ implemented
Div. 2)
an update policy tree_order_statistics_node_update , which, in fact, carries the necessary
amoeba4 → CPI Problemsetting Workshop
operations. Consider them. Most likely, the best way to set the tree is as follows:

typedef tree< errorgorn → Solving Problems with Min Cut

Max Flow Duality
int,
null_type, 1.618034 → Why cheaters in addition to
cheating became RUDE these days??
less<int>,
rb_tree_tag, HellKitsune → Educational Codeforces
Round 17 Editorial
tree_order_statistics_node_update>
ordered_set; pllk → CSES Problem Set new year 2021
update: 100 new problems

If we want to get map but not the set, as the second argument type must be used mapped type. Apparently, ZERO111 → What is the best way to get
the tree supports the same operations as the set (at least I haven't any problems with them before), but negative contribution quickly?

also there are two new features — it is find_by_order() and order_of_key() . The first returns sokolov21lev1 → My "CF-Predictor" doesn't
an iterator to the k-th largest element (counting from zero), the second — the number of items in a set that work???

are strictly smaller than our item. Example of use: shell_lol → Correct me if I am wrong

future_zyl → A suggestion for Christmas

ordered_set X; Almonther → CSES added new tasks 2025

X.insert(1);
X.insert(2); Amr_Coder → Building Adapter Containers
in C++: Implementing Stack and Queue
X.insert(4);
with Different Data Structures
X.insert(8);
Otherwordly → IOI 2025
X.insert(16);
HaykManukyan777 → Codeforces Round
2017
cout<<*X.find_by_order(1)<<endl; // 2
cout<<*X.find_by_order(2)<<endl; // 4 Arpa → IOI vs CF performance: 2024
Edition
cout<<*X.find_by_order(4)<<endl; // 16
cout<<(end(X)==X.find_by_order(6))<<endl; // true MIRAJ12 → DUET Inter-University
Programming Contest (IUPC) 2025 —
contest link and problem set.
cout<<X.order_of_key(-5)<<endl; // 0
Guymmk → CSES New Problems
cout<<X.order_of_key(1)<<endl; // 0
cout<<X.order_of_key(3)<<endl; // 2 Pslnd → Problem recommendation system
cout<<X.order_of_key(4)<<endl; // 2
cout<<X.order_of_key(400)<<endl; // 5 Edvard → Educational Codeforces Round #1

Finally I would like to say about the performance of order_statistics_tree in STL. For this, I provide the k1sara → Codeforces Round #1014 (Div. 2)
following table. Editorial

MathModel → Eolymp Weekend Practice #6

Solution\Problem 1028 1090 1521 1439

flamestorm → Codeforces Round #784 (Div.
4) Editorial
order_statistics_tree, STL 0.062 0.218 0.296 0.468
Detailed →
Segment tree 0.031 0.078 0.171 0.078
0.859*

Binary Indexed Tree 0.031 0.062 0.062 -

* The final task requires direct access to the nodes of the tree for the implementation of solutions for O
(mlogn). Without it, the solution works in O (mlogn*logn).

As you can see from all this , order_statistics_tree relatively little behind handwritten structures, and at times
ahead of them in execution time. At the same time the code size is reduced considerably. Hence we can
conclude is that order_statistics_tree — it is good and it can be used in contests.

Besides tree, I also wanted to describe here trie. However , I was confused by some aspects of its
implementation, greatly limiting its usefulness in programming olympiads, so I decided not to talk about it. If
anyone want he is encouraged to try to learn more about this structure by himself.

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 2 / 19
:
 Useful links:
— Documentation of pb_ds
— Testing of pb_ds
— Using of pb_ds
— Demonstration of order_statistics_tree
— Demonstration of trie with prefix search
— Operations with intervals with handwritten update policy class
— More examples from that site

P.S. Sorry for my poor English :)

stl, k-th order statistic, set, map

+120 adamant 11 years ago 173

Comments (143) Show archived | Write comment?

11 years ago, # | +12

Example of trie with search of prefix range.

Problem: 1414
Solution: http://ideone.com/6VFNZl
→ Reply
adamant

6 years ago, # ^ | ← Rev. 2 0

Is there a way of counting number of strings in the trie with a certain prefix without
iterating through them all?
→ Reply
low_kii_savage

4 years ago, # ^ | 0

You augment the trie node to also contain a number. Update this number
everytime you insert a string into the trie. To get the number of strings which
share the prefix, Just traverse the prefix and output the num in the ending
node.
daksh_
→ Reply

11 years ago, # | +17

Возможно, вам покажутся слегка нетривиальными решения деревом отрезков и деревом Фенвика,
особенно, задач 1521 и 1439. Скорее всего, позже я также предоставлю статью, в которой опишу некоторые
интересные способы использования этих структур, которые редко встречаются.

=======================================================================================
You may be wondered about how I use segment tree and binary indexed tree in my solutions, especially for
adamant problems 1521 and 1439. Most likely, later I'll provide an entry about some interesting ways of using this structures,
which are quite rare.
→ Reply

11 years ago, # ^ | 0

Here it is :)
→ Reply

adamant

11 years ago, # | +21

This is really useful. Thanks a lot!

→ Reply

alex-mercer

11 years ago, # | 0

Very useful article! I need order-statistics on a multiset. How should I define the tree as?
→ Reply

amitsaharana

11 years ago, # ^ | +8

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 3 / 19
:
 As I know, there is no implemented tree multiset in STL. However you can use
pair<T,int> as a key where the second element in pair is the time when item has been
added.
→ Reply
adamant

8 years ago, # ^ | +8

Apparently, you can. Once I tried to write less_equal instead of less and it
started to work as multiset, I even got AC using it in region olympiad)
→ Reply
samatbor

8 years ago, # ^ | ← Rev. 2 +11

I can't erase elements with less_equal comparator, e.g. this code

output "1"
code

So I guess it's not very useful thing (or I do something wrong).

komendart UPD: I can delete iterator which I got with lower_bound. But it
works incorrectly. This code erase 1, not 0
Code
→ Reply

8 years ago, # ^ | 0

Wow. then it really sucks. Seems like I only used it with

insert operations and strangely enough it worked)
→ Reply
samatbor

3 years ago, # ^ | 0

5 years later I can say it is useful in some

problems and this helped me today in this
problem
turzo_sawroop → Reply

3 years ago, # ^ | 0

glad it helped:)
→ Reply
samatbor

3 years ago, # ^ | -13

You can erase elements from the multiset.

1. find the index of the element using

`order_of_key`
2. store it in `idx`
Ranjeet 3. delete using
`s.erase(s.find_by_order(idx))`
→ Reply

7 years ago, # ^ | ← Rev. 2 -8

Well, actually it works fine and exactly does what you

want! The issue is that you're passing
less_equal<int> as the tree comparator. Therefore
it uses the same function for lower_bound() . By
definition of lower_bound function (according to
cplusplus.com) it finds the first element not compared
true . Thus returns the first element greater than
val which is 1 in your example.
Soroush
In order to make sure you may even test
set<int,less_equal<int> > which results the
same.
→ Reply

5 years ago, # ^ | ← Rev. 3 0

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 4 / 19
:
 What if I want to calculate the index of upper_bound of a
particular element? Suppose we have: 1 1 2 3 4 then how
to find index(upper_bound(2))?

saurabhyadavz
UPDATE: Maybe it is = order_of_key(number+1) ?
→ Reply

5 years ago, # ^ | 0

So to erase an element from ordered_set with less_equal I

used lower_bound on (element to be erased — 1) and
then erased the iterator I got from lower_bound and it
works only if the element to be erased is present in the
jnarutoj set.
→ Reply

3 years ago, # ^ | 0

5 years later vol2, lower_bound doesn't work but you can

do it like d.erase(d.find_by_order(d.order_of_key(0)) this
erases iterator correctly, but it's little slow.
nikalla → Reply

2 years ago, # ^ | 0

I don't actually know how does it work, but if you use

upper_bound instead of lower_bound it woulf work
correctly.
YohanLibert → Reply

6 years ago, # ^ | +3

Another drawback of using less_equal instead of less is

that lower_bound works as upper_bound and vice-versa.
Code
roll_no_1
→ Reply

5 years ago, # ^ | 0

An excellent deduction.
→ Reply
klexis

2 years ago, # ^ | 0

Thanks this was helpful

→ Reply
Yash_04k

2 years ago, # ^ | 0

in today's leet c?
→ Reply

VinCenzo___

2 years ago, # ^ | 0

yes bro
→ Reply
Yash_04k

2 years ago, # ^ | 0

https://leetcode.com/contest/weekly-
contest-
342/submissions/detail/938214410/

here is my solution.
VinCenzo___
→ Reply

4 years ago, # ^ | 0

typedef tree<long long, null_type, less_equal<>,

rb_tree_tag, tree_order_statistics_node_update>

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 5 / 19
:
 lamda_cdm indexed_multiset; using " less_equal<> " makes it a multiset
→ Reply

9 months ago, # ^ | ← Rev. 3 0

7 years later, I was using this incorrect template for long time, until
recently ended up messing in live contest here.
https://codeforces.com/contest/1998/submission/275629343
where find() method always returning set.end() and so erase was
wrong. Even lower_bound was giving some wierd behaviour.

Upd. It seems you have to use lower_bound for upper_bound and

vice versa
beyondpluto
Now, i could able to erase as
set.erase(set.upper_bound(x));
And passed
https://codeforces.com/contest/1998/submission/275639066
→ Reply

8 months ago, # ^ | 0

yesss
→ Reply
gautam07.cpp

5 years ago, # ^ | ← Rev. 2 0

What about the comparator i.e. less<int>

→ Reply

venkycodes

6 years ago, # ^ | 0

typedef tree<int, null_type, less_equal, rb_tree_tag,

tree_order_statistics_node_update> indexed_multiset;
→ Reply
__Badral

6 years ago, # ^ | 0

Can we use this in this question? or we can't use it, as I am not able to
implement the multiset part
→ Reply
Gr8

6 years ago, # ^ | +8

just use the fucking binary search on this problem

→ Reply
__Badral

6 years ago, # ^ | ← Rev. 2 0

The 3rd template argument must be less_equal<int> . But adamant, is

it the correct way to do this ? Since as far as I know, most of the STL
containers require a comparator that offers a strict weak ordering (Not sure of
the exact reasons though). So, will there be some drawbacks of trying to
construct a multiset this way?
roll_no_1
→ Reply

4 years ago, # ^ | 0

To use order-statistics on a multiset: Use:: tree<int, null_type, less_equal, rb_tree_tag,

tree_order_statistics_node_update> s;

find_by_order and order_of_key work the same as for a set.

pranav.vinchurkar However for searching, lower_bound and upper_bound work oppositely. Also, let's say
you want to erase x, use s.erase(s.upper_bound(x)) (as upper bound is considered as
lower bound)
→ Reply

3 years ago, # ^ | 0

This is actually great. Whenever I needed to handle duplicate I used take

pair<val,index>. This is much simpler.
→ Reply

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 6 / 19
:
 GooglerPraveen
→ Reply

11 years ago, # | ← Rev. 2 0

.(same comment as above)

→ Reply

amitsaharana

10 years ago, # | 0

what will be the complexity of erase operation? O(logn) or O(n)

→ Reply
ravishmahur

10 years ago, # ^ | 0

O(logn)
→ Reply

adamant

7 years ago, # ^ | 0

Really??
→ Reply
ILoveDoraemon

7 years ago, # ^ | 0

Yes.
→ Reply

adamant

10 years ago, # | 0

Is there any efficient function to merge 2 trees ?

→ Reply

rajat1603

7 years ago, # ^ | +1

You can do in log(n) if the greatest element of 1 tree is smaller than smallest of other.
Otherwise, I don't you have a better option. Tell me as well if you have found
something interesting.
Stecher → Reply

7 years ago, # ^ | 0

How do you merge two non-intersected rbtrees (as in the article) in O(lg n)
time? I find that the default join() function takes linear time...
→ Reply
0w1

6 years ago, # ^ | 0

Have you found something interesting about merge ? Im trying to

do .join but it throws error.
→ Reply
kuksag

10 years ago, # | 0

how can i use it like multiset ?

→ Reply
draak_krijger

10 years ago, # ^ | 0

Main idea is to keep pairs like {elem, id}.

typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 7 / 19
:
 tree_order_statistics_node_update> ordered_set;

int t = 0;

adamant
ordered_set me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";
→ Reply

10 years ago, # ^ | 0

thanks a lot :)
→ Reply
draak_krijger

7 years ago, # ^ | 0

like me.order_of_key({x, 0}) me.find_by_order({x,0}) dose not work.. why??

→ Reply
shishir.hstu

7 years ago, # ^ | 0

*me.find_by_order({x,0})
→ Reply

Dalgerok

7 years ago, # ^ | 0

still it does not work.

→ Reply
shishir.hstu

6 years ago, # ^ | 0

sure it does work, but you cannot print a pair so

you have to do it like this cout <<
me.find_by_order(1)->first ;
MasterMind
→ Reply

7 years ago, # ^ | 0

wtf, find_by_order takes number

→ Reply

adamant

6 years ago, # ^ | 0

how to use find_by_order if I'm using

ordered_set with pairs. ~~~~~ typedef tree<
pair<int, int>, null_type, less<pair<int, int>>,
rb_tree_tag, tree_order_statistics_node_update>
GlobalElite ordered_set; ~~~~~
→ Reply

5 years ago, # ^ | 0

nice technique. worked fine! thanks a lot.

→ Reply
orange_trie

6 years ago, # ^ | 0

typedef tree<int, null_type, less_equal, rb_tree_tag,

tree_order_statistics_node_update> indexed_multiset;
→ Reply
__Badral

9 years ago, # | 0

Hi, adamant, the code files in Useful Links don't seem to work. Could you fix them?

Thanks for this great post. I am looking forward to your next and next next posts.

→ Reply

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 8 / 19
:
 duckladydinh
→ Reply

9 years ago, # ^ | 0

Can you elaborate please?

→ Reply

adamant

9 years ago, # ^ | ← Rev. 2 0

For example, the code in "Demonstration of trie with prefix search" cannot
run on my computer. I saw that there was some old syntax like the
namespace pb_ds. I changed it, then it returned a new error in another place.
The truth is I am not good enough to change things any more. I hope that you
can update it. (I know that I can use the trie code in one of your comments,
but this post would be even better if the cost in Useful Links were also
updated)
duckladydinh

Thank you.
→ Reply

9 years ago, # ^ | +1

I can't edit the original files — they're not mine. But here is the
correct version: http://ideone.com/BpZlYO
→ Reply
adamant

9 years ago, # ^ | 0

Thank you.
→ Reply
duckladydinh

8 years ago, # | 0

https://www.e-olymp.com/ru/problems/2961 Is it possible to solve this problem using this

algorithm?
→ Reply
Dalgerok

8 years ago, # | +1

Can anybody share a Java equivalent class for this type of set or a code which acts according to
above data structure?
→ Reply
coderbond007

8 years ago, # ^ | ← Rev. 2 0

It does not exist.

You may use instead:

self-written tree
treap
dalex
numbers compression + fenwick tree
→ Reply

8 years ago, # ^ | 0

I thought of number compression + fenwick tree, but this solution will work
for only offline queries. I want to handle online queries. The best I can think of
now is Treap + Segment Tree or Treap + Fenwick Tree. But here again is the
problem of implementation of mixed data structure, I am unable to think how
coderbond007 to implement that. Can you please help me?
→ Reply

7 years ago, # | 0

Any idea on how to use this pre C++11?

→ Reply
lnzva

7 years ago, # | 0

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 9 / 19
:
 How can I use a custom compare function in the "Key comparison functor" section for custom
data types?
→ Reply

Tanmoy_Datta

7 years ago, # ^ | 0

Just like for regular set..

→ Reply

adamant

7 years ago, # ^ | 0

I can use custom compare function for a set by using operator overloading. I
want to know is there any other way to do this for both set and ordered set
using lambda expression or just using a compare bool function?

Thank adamant you very much for your nice post.

Tanmoy_Datta
→ Reply

7 years ago, # ^ | ← Rev. 2 +3

I suppose you can overload operator and still use less<T> .

Also you can use functors and lambdas in the way similar as for
sets:

auto cmp = [](int a, int b){return a < b;};

tree<int, null_type, decltype(cmp)> x(cmp);
tree<int, null_type, function<bool(int, int)>> y([]
adamant (int a, int b) {

return a < b;});

→ Reply

5 years ago, # ^ | 0

Why does it only work with lambdas and not functions?

On doing

tree<pair<int, int>, null_type,

decltype(&comp), rb_tree_tag,
tree_order_statistics_node_update>
PyAlpha
ordered_set(&comp);

Where comp is a comparator function, I get an error.

→ Reply

3 years ago, # ^ | 0

It does not work for me. I tried using custom comparator

but getting error. Please resolve my issue. Code Link:
https://leetcode.com/submissions/detail/693650301/

I have written cmp struct but when i pass in tree argument

sangramsinh
it is giving me error.
→ Reply

3 years ago, # ^ | ← Rev. 2 0

Sorry, what doesn't work?

struct cmp{
bool operator() (const int &a,const int &b){
return a <= b;
}
};

typedef
tree<int,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>
adamant ordered_set;

works just fine on my side.

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 10 / 19
:
 P.S. I would really recommend against using <= as a comparator, because it's
supposed to be anti-reflexive.
→ Reply

7 years ago, # | 0

Is it possible to search for the order of a non-key value by passing a comparator/function ? I

sometimes find myself have to use my own tree templates instead because of having to write a
search function that can cope with this task.
→ Reply
haleyk100198

7 years ago, # | +6

What is the constant factor of order_statistics_tree though it executes in logarithmic complexity

? I think it's constant factor is very high.
→ Reply
Jubair_2147483647

7 years ago, # | 0

could anyone write the exact thing to use this data structure as map..pls.I'm not able do so.
→ Reply

ram_24

7 years ago, # ^ | 0

And what exactly do you want from it? You can use something like that.

#include<ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template<class key, class value, class cmp = std::less<key>>

using ordered_map = tree<key, value, cmp, rb_tree_tag,
adamant
tree_order_statistics_node_update>;

ordered_map<int, int> my_map;

→ Reply

7 years ago, # ^ | 0

as it was mentioned in the article that we can use it as map by defining

mapped type .So I tried to do that by couldn't. that's all;)
→ Reply
ram_24

7 years ago, # ^ | 0

is this thing a order statistics tree

→ Reply
des1997

6 years ago, # ^ | 0

Can you write the multiset implementation of ordered_set. When I use

less_equal then I'm not able to erase from the ordered_set. And when I use
the pair for including duplicates I'm not able to use find_by_order({x,0}).
amankumarkeshu
→ Reply

6 years ago, # ^ | 0

What's wrong with find_by_order({x, 0})?

→ Reply

adamant

6 years ago, # ^ | 0

It gives an error. It says no known conversion. error: no matching

function for call to '__gnu_pbds::tree<std::pair<int, int>,
__gnu_pbds::null_type, std::less<std::pair<int, int> >,
__gnu_pbds::rb_tree_tag,
amankumarkeshu __gnu_pbds::tree_order_statistics_node_update>::find_by_order()
→ Reply

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 11 / 19
:
 6 years ago, # ^ | 0

Wait, find_by_order takes number k and returns

k -th element. What exactly do you expect it to
return?..
adamant → Reply

6 years ago, # ^ | 0

A number .
→ Reply
amankumarkeshu

6 years ago, # ^ | 0

I think you should use

order_of_key then
→ Reply
adamant

6 years ago, #0
^ |
Thanks adamant I
did that.
amankumarkeshu → Reply

6 years ago, # ^ | ← Rev. 2 0

Actually find_by_order( x) takes in an integer input

because it tells us the element present in the position x.
Whereas find_by_order({x, 0}) is a syntax error and it wont
amankumarkeshu work.
→ Reply

7 years ago, # | 0

can we use it as multiset?

→ Reply

ram_24

7 years ago, # ^ | 0

u can use pair<int,int> for manage the duplicate values..

→ Reply

aasom143

6 years ago, # ^ | 0

typedef tree<int, null_type, less_equal, rb_tree_tag,

tree_order_statistics_node_update> indexed_multiset;
→ Reply
__Badral

6 years ago, # ^ | ← Rev. 2 0

It is:

typedef tree<int, null_type, less_equal<int>,

rb_tree_tag, tree_order_statistics_node_update>
indexed_multiset;
CodeKracker
→ Reply

5 years ago, # ^ | 0

thank you bro :) it worked for duplicate elements too..

→ Reply
_Chaitanya1999

5 years ago, # ^ | 0

what to do if i want to merge two ordered multisets?

→ Reply

PritamDas

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 12 / 19
:
 6 years ago, # | 0

How can I erase element from order_set by it's value?

Vladikus004 → Reply

6 years ago, # ^ | +1

just do ordered_set<T> st; st.erase(key);

→ Reply
oToToT

6 years ago, # ^ | 0

This doesn't work .

→ Reply
amankumarkeshu

6 years ago, # ^ | 0

ordered_set :: iterator it; it=st.upper_bound(key); st.erase(it); it

works;
→ Reply
prateekrai

6 years ago, # ^ | 0

Thanks bro
→ Reply
amankumarkeshu

4 years ago, # ^ | +3

You can try this to erase by value from ordered multiset(or wwhatever it's called in
technical terms)

How to use Ordered Multiset

typedef tree<int, null_type, less_equal<int>, rb_tree_tag,

tree_order_statistics_node_update> ordered_set;
prabhav_
To erase by value from Ordered Multiset:
os.erase(os.find_by_order(os.order_of_key(val)));
→ Reply

4 months ago, # ^ | 0

this was very helpful i did not want to modify the data structure by
modifying it to contain <key,value>pair but wanted to use provided function
of stl
singularityisthestart → Reply

6 years ago, # | 0

(Sorry for necroposting) Does anyone know how to compile with the pbds header files on Mac
OS X ? I think the g++ command is configured to use clang by default, and so it is not directly
available. I've tried adding ext/pb_ds into the include folder (the same way you would enable
bits/stdc++.h) but instead new dependencies come up.
andaanda
→ Reply

5 years ago, # ^ | 0

For me, I installed the latest version of gcc (gcc 9.3.0_1) and compiled with gcc-9. It
works on Mojave and Catalina and it should work on High Sierra (but I haven't tested
it).

To install gcc-9, I used brew and the command brew install gcc@9
Pa.Nic
→ Reply

4 years ago, # ^ | 0

(Again, sorry for necroposting) There is an important step that I've so-far seen
all the mac g++ setup instructions ignore/skip. I also installed gcc through
brew, but neither bits/stdc++.h header nor pbds data structures seemed to
work. Putting the bits/stdc++.h file manually in the /usr/local/include folder
allowed me to at least solve the header problem, but trying the same method
for pbds spawned a lot of dependency issues.

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 13 / 19
:
 The problem was that brew sets up the g++ command as g++-10 so that it
doesn't clash with the default g++ command mac provides. So, alias-ing g++
to g++-10 in the .bashrc/.zshrc file would be enough for solving the issue if
you compile using the terminal. But if you compile using an editor and the
editor directly uses the /usr/bin/g++ binary for compilation, then alias-ing g++
DrSwad wouldn't work anymore. For example, most of the popular VSCode
extensions for CP I've seen use /usr/bin/g++ to compile. I wasn't aware that
this was the root of the issue and had been missing pbds structures for a
long time. The way to solve it is to simlink g++ to g++-10 and prepend it to
the PATH variable so that the simlink is prioritized before the default g++.
Instructions for the simlink way

I might even find it useful myself if I ever need to setup a mac again in future.
→ Reply

2 years ago, # ^ | 0

(Sorry for Necroposting). But I have to update the details as from

M1 onwards (possibly Big Sur) configurations have been changed.
The Cellar directory is not available at /usr/local
anymore. You can do the following instead.

cd /opt/homebrew/Cellar/gcc/12.2.0/bin

ln -s ./c++-12 ./c++

ln -s ./g++-12 ./g++
Nanda
export
PATH=“/opt/homebrew/Cellar/gcc/12.2.0/bin:$PATH”

Did you manage to solve PBDS issue on your mac ? Doing all
above doesn't solve the PBDS issue.
→ Reply

2 years ago, # ^ | 0

Thanks for the updates.

Yes, PBDS seems to work for me. I'm running macOS

Ventura on M1 (Btw I had to reinstall the command-line
tools when updating from Big Sur to Ventura). Can you
elaborate on the exact issue you're facing, or possibly
provide some error logs?

Also, did you try compiling a source code that uses PBDS
DrSwad from the terminal? Because I've fixed similar issues for
others who were compiling/running from an editor/IDE,
but the main culprit was actually the editor. The editor
might fail if you didn't properly point it toward the
Homebrew g++.
→ Reply

2 years ago, # ^ |
I am also using ventura 13.2 on M1. I tried both on sublime build and manually on terminal to run a sample code. It shows
error.

In file included from B.cc:13:

/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/ext/pb_ds/assoc_containe
fatal error: 'bits/c++config.h' file not found
#include <bits/c++config.h>
Nanda
The .zshrc profile looks like as mentioned in the above command. I tried to add the missing file, then got reported for
missing file and so on. In fact the ext/pb_ds directory I put there myself.
→ Reply

2 years ago, # ^ |
I think it might have to do with the configs in .zshrc . I checked my .zshrc file and there seem to be som

eval "$(/opt/homebrew/bin/brew shellenv)"

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 14 / 19
:
 # g++
CPLUS_INCLUDE_PATH=/opt/homebrew/Cellar/gcc@12/12.1.0_1/include/c++/12:/opt/homebrew
export CPLUS_INCLUDE_PATH
export PATH=/opt/homebrew/Cellar/gcc@12/12.1.0_1/bin:$PATH

# other configs ...

DrSwad
Check if you have similar paths and modify them accordingly before putting them in .zshrc . Also, the last p
template and testlib.h in there, so that they always get included in every program on my PC and the edito

Also, try reinstalling command-line tools with xcode-select --install .

Let me know if they resolve your issue.

→ Reply

6 years ago, # | ← Rev. 2 +6

Note on using less_equal as comparison function to use it as a multiset:

_GLIBCXX_DEBUG must not be defined, otherwise some internal check will fail.
find will always return end .
lower_bound works like upper_bound in normal set (to return the first element > it)
upper_bound works like lower_bound in normal set (to return the first element >= it)
a61742 find_by_order and order_of_key works properly (unlike the 2 functions above).

Some code to verify the points above: Try it online!

→ Reply

6 years ago, # | ← Rev. 2 0

adamant, while discussion, someone suggested that the time complexity of using it as a set is
amortized log(n), and this post says that it means that in some cases that can be O(n). I wonder
if that is true ?? If yes, is there an alternative to policy based data structures ?? Here is one
solution
harshraj22
→ Reply

6 years ago, # ^ | 0

It shouldn't be. And even if so, what's the deal? It will always be O(n log n +q log n) if
you use set of numbers of size n and run q queries.
→ Reply
adamant

6 years ago, # ^ | 0

but this link line 4 says :

> while having an amortized complexity of O(lgn) means that

some (very few) operator calls can take O(n) time.

and if that's the case, won't the complexity be q*n instead of qlog(n) ??
which I suspect might be the reason of my solution getting TLE using policy
harshraj22 based data structure while the editorial using treap and getting accepted
(having same time complexity ).

Please guide me through it as I use this data structure very frequently.

→ Reply

6 years ago, # ^ | 0

It can't be. By definition amortized complexity means that algorithm

is guaranteed to have such executing time if it's divided By the
numbers of queries. When they say "few" they mean it
→ Reply
adamant

6 years ago, # ^ | 0

So, I should treat it as the worst time complexity of this

data structure ?
→ Reply
harshraj22

6 years ago, # ^ | +1

If you don't revert operations and don't need it

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 15 / 19
:
 persistent then basically yes. In your case it is
likely to be too large constant factor. But I'll look
into it later.
→ Reply
adamant

5 years ago, # | 0

Thanks,it just got me an AC.

→ Reply
yogi

5 years ago, # | 0

If someone is having trouble to use these in windows with mingw compiler, try to find
hash_standard_resize_policy_imp.hpp0000644 in
MinGW\lib\gcc\mingw32\6.3.0\include\c++\ext\pb_ds\detail\resize_policy and rename it to
hash_standard_resize_policy_imp.hpp. I dont know why it is named like this.
mub.ch → Reply

5 years ago, # ^ | 0

thanks bro ...do you know why it name like this ... why wrong extension is given to it..
→ Reply
mohitsamant

5 years ago, # | 0

I have defined a bool cmp(pair<int,int> a, pair<int, int> b) for comparing

pairs. Is it possible to use that as the comparator for the ordered_set ?
→ Reply
saarang

5 years ago, # | 0

Thank you this really helped me.

→ Reply
Flower08

5 years ago, # | 0

Is this actually STL? I only see files with gcc's implementation of the c++ standard library. Actual
STL is quite old (the linked post references SGI's docs, and SGI doesn't even exist any more)
→ Reply
ben_dover

5 years ago, # ^ | +1

Nope, this has nothing to do with the C++ standard library.

→ Reply
jef

5 years ago, # | ← Rev. 2 +1

This is a GNU extension, so it has nothing to do with the STL which (incorrectly) refers to the
C++ standard library.
→ Reply
jef

5 years ago, # ^ | 0

STL doesn't even refer to the C++ standard library. STL is the Standard Template
Library from long ago which heavily influenced the C++ standard library but is not the
same thing. https://stackoverflow.com/a/5205571
→ Reply
ben_dover

5 years ago, # ^ | ← Rev. 3 0

I know, but here and in many other places "STL" is incorrectly used to refer to
the C++ standard library.
→ Reply
jef

5 years ago, # | +3

The first returns an iterator to the k-th largest element (counting

from zero)

Shouldn't it be the k-th smallest element ? adamant

→ Reply

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 16 / 19
:
 hieplpvip → Reply

5 years ago, # | 0

How to merge two ordered sets?

→ Reply

PritamDas

5 years ago, # ^ | 0

Iterate through every element in the smaller set and append it to the bigger one
→ Reply

adderall

5 years ago, # ^ | 0

thanks brother
→ Reply

PritamDas

5 years ago, # | 0

When to use BIT over PBDS other then memory limit

→ Reply

Zuciso

5 years ago, # ^ | 0

https://codeforces.com/contest/459/problem/D can we solve this question using pbds

? Its giving me runtime error —
https://codeforces.com/contest/459/submission/81689503
→ Reply
Zuciso

5 years ago, # | 0

can we use pair in place of int ??

→ Reply

iabhishek15

5 years ago, # ^ | 0

Sure, why not. We may use any type with operator < defined.
→ Reply

adamant

5 years ago, # | 0

Is insert not too slow? I tried 10^7 insertions and it took over a minute.
→ Reply
participant123

4 years ago, # | 0

Doesn't find_by_order(k) returns the kth smallest element in the set? In the article the values
given seems like the kth smallest ones not the largest ones
→ Reply
anshjain18

3 years ago, # | ← Rev. 2 0

Just saw this post and I am wondering can

https://codeforces.com/contest/237/submission/2804338 be the first submission using pbds? (I
did not actually used pbds in this submission just included it as part of my template.) IIRC,
Gerald used to see my usage of this trick in Dec, 2013 and asked about its usage.
boleyn.su → Reply

3 years ago, # | 0

Can I make the ordered set get the first element greater than x or even greater than or equal?
→ Reply

Sameh.Sayed14

3 years ago, # ^ | 0

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 17 / 19
:
 *find_by_order(order_of_key(x)) -- this will be first greater or equal element than x if u
wanna only greater *find_by_order(order_of_key(x+1)) <-- write this
→ Reply
nikalla

2 years ago, # | ← Rev. 2 0

Please note erase(key) does not work if you are using ordered_map typedef
tree< int, map_value_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_map;
jyoti851999 → Reply

21 month(s) ago, # | 0

Thanks a lot bro

→ Reply

BitSlayer

17 months ago, # | 0

can we use this in IOI

→ Reply

Muhammad_Aneeq

9 months ago, # | 0

Could not implement it in time for today's E :(

→ Reply

aqua4

9 months ago, # ^ | 0

I also used this for the E today, but I found this blog was too confusing so I used this
tutorial instead: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ lmao.
xug → Reply

4 months ago, # | 0

12 Years Later...
1) While going through the official documentation of Policy Based Data Structures , I found an
internal test claiming that `ov_tree_tag' is better for split and join methods.

The test can be found here.

2) Moreover, we can't use tree_order_statistics_node_update with the

ov_tree_tag .

ntt_not_found
I can't find any proof for this :(

3) After some years, the links to some of the codes seem to be down. They can be found in this
git repository.

Thank you for this amazing blog !

→ Reply

2 months ago, # | +1

For Anyone who wants to try this concept

1915F - Greetings This question is a good and simple implementation of ordered set.
→ Reply
sk091105

Codeforces (c) Copyright 2010-2025 Mike Mirzayanov

The only programming contests Web 2.0 platform
Server time: May/12/2025 06:55:03UTC+7 (l2).

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 18 / 19
:
 Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions

Supported by

https://codeforces.com/blog/entry/11080?mobile=false 10 14 12/05/2025
Trang 19 / 19
: