[HN Gopher] Segment Tree ___________________________________________________________________ Segment Tree Author : pmoriarty Score : 75 points Date : 2020-10-01 12:25 UTC (1 days ago) (HTM) web link (cp-algorithms.com) (TXT) w3m dump (cp-algorithms.com) | aliceryhl wrote: | Segment trees are my favorite data structure. I wrote a library | with them: https://crates.io/crates/segment-tree | yougaindra wrote: | interesting, does it support lazy updates? | ekzhang wrote: | 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 | munhitsu wrote: | feels like a plant for the CRDT garden | AaronFriel wrote: | 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/ | SamReidHughes wrote: | 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. | miguendes wrote: | 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 wrote: | 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 wrote: | Windowed aggregation is a common problem in feature | engineering. We use segment trees to solve it. | https://youtu.be/0HttRa2cXig ___________________________________________________________________ (page generated 2020-10-02 23:00 UTC)