Dear All,

How to access to *i*th element of a set in c++ effectively (*O(1) or (logN)*)?

Thanks

# | User | Rating |
---|---|---|

1 | Um_nik | 3538 |

2 | tourist | 3509 |

3 | Benq | 3473 |

4 | ecnerwala | 3446 |

5 | ksun48 | 3432 |

6 | maroonrk | 3404 |

7 | Radewoosh | 3383 |

8 | yosupo | 3324 |

9 | boboniu | 3300 |

10 | apiadu | 3238 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 191 |

4 | antontrygubO_o | 185 |

4 | pikmike | 185 |

6 | Um_nik | 184 |

7 | Ashishgup | 182 |

8 | vovuh | 181 |

9 | pashka | 168 |

9 | Radewoosh | 168 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2020 08:59:32 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

There is no documented way to do this. But set is a RB-tree, so you probably can get access to tree's structure and get i-th element in by yourself. I don't think it's a good way

But how to fetch

i-thelement from RB-tree itself in O(logN) without precalculation?I don't know, that's true. Well, it looks like one does not simply access k-th element of

`set<>`

What means kth element in Set if the set is unordered?

Surely only ordered sets (for example TreeSet in java) are considered. It looks like set in c++ is implemented in the same way and is ordered therefore.

The trouble is that none of the tree-like data structures available in the standard libraries support a fast k-th element query ("given k, find the k-th smallest of the stored numbers").

The thing you have to add to a canonical balanced tree structure is information about subtree sizes: for each node in the tree, keep the count of elements in the subtree rooted at this node. For a particularly easy-to-implement balanced tree structures, check out splay trees and treaps.

(c) http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm310

You forgot to mention the decreased efficiency of insert/remove for tree with info on branch sizes (up to O(n), I think). You see, it is just a way of precalculation.

More obvious precalculation is, surely, to dump the set into an array and then to make as many queries as necessary.

UPD: I think I am wrong and efficiency of inserting/removing may remain O(logN), sorry.

There is a cheat to access Parent, Left and Right nodes. But i have no idea how to use this information "online". There is problems because of tree modifications — rotations and other balancing stuff while inserting or erasing nodes.

Some discussion about maintaining subtree sizes: http://online-judge.uva.es/board/viewtopic.php?p=42339&sid=06bcbb8c183b8bea4de63a3fa44fb3f2#p42339

Hey! Looks like there's a way to do it after all. Please see http://codeforces.com/blog/entry/11080

No there isn't!. That is another implementation!

You can use C++ SGI STL

`tree`

.For example:

how can we make ordered_multiset ?

Use

`pair<T, size_t>`

as element and give each element an unique id.False. assoc_container.hpp is enough.

I found something pretty crazy while using this data structure for the first time.

I tried to test it a bit before using it in my real problem, and I was surprised to see that

it was incredibly slow.It compiled but, still, it took around 50s just to do

So I gave up and I used a segment tree instead, but in fact the segment tree wasn't perfect for the problem and I ended with only 42 / 140 on this problem (today's COCI#2, problem 5)

Now, I tried to see what went wrong and I found the culprit : -D_GLIBCXX_DEBUG Without that option, I can insert 10

^{6}elements in 0.6s, and that's honest for .Morality: never trust your complier options :D

Thanks for this tip, this is totally awesome!

find_by_order takes O(N) where N is size of ordered set

How about binary search? You have lower_bound() for set. Please correct me if I am wrong. The complexity is log(n)*log(L) though. L= range of values in set,n=no. of values in set.

int idx=(int)(S.lower_bound(start,end,value)-S.begin()) if idx>k , search again.

The problem here is

`operator -`

— it works in linear time. Iterators used by`set`

are bidirectional only, not random access. It means that you can relatively fast increase/decrease them, but you cannot make bigger jumps or subtract them fast than in a linear time (more precisely, inO(answer)).So if we take the lower_bound value from set is

O(log n)while taking the position of it isO(n)complexity ?!Correct.

Thanks for sharing new things ^^ I will keep mind this so that never get TLE for stupid reasoning ^^

Does anyone know of something similar in Java?

Yes. Create Balanced BST <3