4 ms·

Segment Tree

128 points by pmoriarty 6y ago

miguendes 6y ago
Segment is really nice. My first contact was when I was training for ICPC. But then I never had opportunity to use it professionally. I'm curious to know if anybody has used it to solve a real problem.
- thomasahle 6y ago
  In real life you often need trees that can insert and delete, and so you need balancing. Luckily you can usually avoid that at ICPC since it would take forever to code.
- nikhilsimha 6y ago
  Windowed aggregation is a common problem in feature engineering. We use segment trees to solve it. https://youtu.be/0HttRa2cXig https://youtu.be/0HttRa2cXig
munhitsu 6y ago
feels like a plant for the CRDT garden
AaronFriel 6y ago
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.
aliceryhl 6y ago
Segment trees are my favorite data structure. I wrote a library with them: https://crates.io/crates/segment-tree https://crates.io/crates/segment-tree
- yougaindra 6y ago
  interesting, does it support lazy updates?
  - aliceryhl 6y ago
    Yes, that's the point of a segment tree.
ekzhang 6y ago
As a competitive programmer (IOI gold medalist / ICPC world finalist), segment trees are really the most classic and versatile data structure seen in competitive programming. In addition to the basic idea, there are problems that can be solved with all sorts of different variations - segment trees with lazy propagation, sparsity, persistence, Li-Chao queries, 2D queries, etc. There's an extremely optimized, 10-line, iterative C++ implementation of the basic data structure due to Oleksandr Bacherikov. https://codeforces.com/blog/entry/18051 https://codeforces.com/blog/entry/18051 Also see Fenwick trees: logarithmic-time range queries in 3 lines of C code. https://en.wikipedia.org/wiki/Fenwick_tree https://en.wikipedia.org/wiki/Fenwick_tree
gen220 6y ago
Segment trees are one of those data structures that blew my mind when I first learned about them. They felt like “cheating”. :) Take a look at “union-find” and tries, too, for some other classic CP structures that most normal data structures and algorithms classes don’t cover. Also, FYI, the code renders in an unreadably-large font on mobile. Otherwise this is a great resource! Thank you for putting it together.

128 points by pmoriarty 6y ago

Segment is really nice. My first contact was when I was training for ICPC. But then I never had opportunity to use it professionally. I'm curious to know if anybody has used it to solve a real problem.

thomasahle 6y ago
In real life you often need trees that can insert and delete, and so you need balancing. Luckily you can usually avoid that at ICPC since it would take forever to code.
nikhilsimha 6y ago
Windowed aggregation is a common problem in feature engineering. We use segment trees to solve it. https://youtu.be/0HttRa2cXig https://youtu.be/0HttRa2cXig

munhitsu 6y ago

feels like a plant for the CRDT garden

AaronFriel 6y ago

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.

aliceryhl 6y ago

Segment trees are my favorite data structure. I wrote a library with them: https://crates.io/crates/segment-tree https://crates.io/crates/segment-tree

yougaindra 6y ago
interesting, does it support lazy updates?
- aliceryhl 6y ago
  Yes, that's the point of a segment tree.

ekzhang 6y ago

As a competitive programmer (IOI gold medalist / ICPC world finalist), segment trees are really the most classic and versatile data structure seen in competitive programming. In addition to the basic idea, there are problems that can be solved with all sorts of different variations - segment trees with lazy propagation, sparsity, persistence, Li-Chao queries, 2D queries, etc. There's an extremely optimized, 10-line, iterative C++ implementation of the basic data structure due to Oleksandr Bacherikov. https://codeforces.com/blog/entry/18051 https://codeforces.com/blog/entry/18051 Also see Fenwick trees: logarithmic-time range queries in 3 lines of C code. https://en.wikipedia.org/wiki/Fenwick_tree https://en.wikipedia.org/wiki/Fenwick_tree

gen220 6y ago

Segment trees are one of those data structures that blew my mind when I first learned about them. They felt like “cheating”. :) Take a look at “union-find” and tries, too, for some other classic CP structures that most normal data structures and algorithms classes don’t cover. Also, FYI, the code renders in an unreadably-large font on mobile. Otherwise this is a great resource! Thank you for putting it together.