Segment Tree | Hacker News Reader

Segment Tree

cp-algorithms.com

128 pointspmoriarty16 comments

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

Also see Fenwick trees: logarithmic-time range queries in 3 lines of C code.

https://en.wikipedia.org/wiki/Fenwick_tree

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.

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.

Windowed aggregation is a common problem in feature engineering. We use segment trees to solve it. https://youtu.be/0HttRa2cXig

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.

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

interesting, does it support lazy updates?

Yes, that's the point of a segment tree.

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://andrew.gibiansky.com/blog/haskell/finger-trees/

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.

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

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

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.

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

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.

feels like a plant for the CRDT garden

Reply on news.ycombinator.com