3 ms·

Finger trees (and other BSTs) are probably too slow for problems meant to be solved by segment trees. The problem is that in competitive programming you receiv

by uyt 6y ago

Finger trees (and other BSTs) are probably too slow for problems meant to be solved by segment trees. The problem is that in competitive programming you receive your entire input at the beginning. So you never need to "rebalance" anything since you always know exactly where data needs to be filled/deleted (sometimes needing a coordinate compression step). This lets you work with a static complete binary tree which is extremely cache friendly and simple to code. Augmented balanced search trees are still useful in competitive programming but are much rarer: https://cp-algorithms.com/data_structures/treap.html https://cp-algorithms.com/data_structures/treap.html

kadoban 6y ago
Mostly true in general, but not universal. BSTs and other trees (even ones not embedded in arrays) are seen in competitive programming. Sometimes they're almost forced, and sometimes the time bounds are just lax enough that it's fine. And there are some problems you're forced to do "online", you don't always usefully get your data in advance. There's tricks problem setters do to force online processing, usually just making the input a series of separate queries and having the _real_ input depend on the answer to the previous query.
- uyt 6y ago
  Yea I know what you mean. Here's an example problems where the input is encrypted by the previous answer: https://codeforces.com/contest/455/problem/D https://codeforces.com/contest/455/problem/D And of course there are problems that are interactive IO too. But generally speaking in most problems where treaps/splay trees aren't intended, the time limits are too tight to use them. You can barely hit 10^5 ops/sec using them but that's the typical N and Q for seg tree problems.
  - kadoban 6y ago
    Yeah definitely true. I feel like sites that allow many languages have a hard time really ruling out the efficiency differences between most optimal and close-to-the-right-asymptotics.

by uyt 6y ago

kadoban 6y ago

Mostly true in general, but not universal. BSTs and other trees (even ones not embedded in arrays) are seen in competitive programming. Sometimes they're almost forced, and sometimes the time bounds are just lax enough that it's fine. And there are some problems you're forced to do "online", you don't always usefully get your data in advance. There's tricks problem setters do to force online processing, usually just making the input a series of separate queries and having the _real_ input depend on the answer to the previous query.

uyt 6y ago
Yea I know what you mean. Here's an example problems where the input is encrypted by the previous answer: https://codeforces.com/contest/455/problem/D https://codeforces.com/contest/455/problem/D And of course there are problems that are interactive IO too. But generally speaking in most problems where treaps/splay trees aren't intended, the time limits are too tight to use them. You can barely hit 10^5 ops/sec using them but that's the typical N and Q for seg tree problems.
- kadoban 6y ago
  Yeah definitely true. I feel like sites that allow many languages have a hard time really ruling out the efficiency differences between most optimal and close-to-the-right-asymptotics.