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