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.
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.
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.
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.