5 ms·

This seems like a slightly less optimized, simpler form of finger trees, which are more common in pure functional languages as a persistent data structure. Fin

This seems like a slightly less optimized, simpler form of finger trees, which are more common in pure functional languages as a persistent data structure. Finger trees can be paired with a monoidal function efficiently which is recomputed on node insertion and removal. This segment tree looks like an in-place version of a finger tree that's a bit harder to extend. Finger trees are a great tradeoff data structure with constant time insertion at the end or beginning, constant time reversal (forward and backward traversal), log n merge and split, and log n random access insertion. Just a wonderful data structure. https://en.wikipedia.org/wiki/Finger_tree https://en.wikipedia.org/wiki/Finger_tree https://andrew.gibiansky.com/blog/haskell/finger-trees/ https://andrew.gibiansky.com/blog/haskell/finger-trees/

SamReidHughes 6y ago
The actual important feature of segment trees is range updates. Having a monoidal function to update interior nodes isn't specific to finger trees -- every tree can do this in its internal nodes, it's a common data structures technique.
contravariant 6y ago
Not sure if 'less optimized' is the right term, the way I understand it you can implement a basic segment tree as a single contiguous array (unless of course you're storing more complicated data structures in each node). Something like that is way easier to optimize than a finger tree which require type polymorphism to be even remotely workable. Of course finger trees do allow for easier insertion and deletion, so they're superior if you need that (although it's surprising how much you can get away with by just rebuilding the whole structure when necessary).
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.

SamReidHughes 6y ago

The actual important feature of segment trees is range updates. Having a monoidal function to update interior nodes isn't specific to finger trees -- every tree can do this in its internal nodes, it's a common data structures technique.

contravariant 6y ago

Not sure if 'less optimized' is the right term, the way I understand it you can implement a basic segment tree as a single contiguous array (unless of course you're storing more complicated data structures in each node). Something like that is way easier to optimize than a finger tree which require type polymorphism to be even remotely workable. Of course finger trees do allow for easier insertion and deletion, so they're superior if you need that (although it's surprising how much you can get away with by just rebuilding the whole structure when necessary).

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.