[HN Gopher] Grokking Fenwick Trees
       ___________________________________________________________________
        
       Grokking Fenwick Trees
        
       Author : jornhub
       Score  : 55 points
       Date   : 2021-08-30 11:41 UTC (1 days ago)
        
 (HTM) web link (jornhub.dev)
 (TXT) w3m dump (jornhub.dev)
        
       | vanderZwan wrote:
       | To be fair to the original paper by Peter Fenwick, it is quite a
       | clear and accessible paper by academic standards (but this
       | article is still very welcome and even easier to follow).
       | 
       | I especially liked the technique for isolating the least
       | significant set bit, and have sometimes wondered if there are any
       | other places one might use it. Has anyone here ever used that
       | trick in a different context?
        
       | nayuki wrote:
       | I have no explanations but runnable code:
       | https://www.nayuki.io/page/binary-indexed-tree
        
       | Syzygies wrote:
       | This is beautiful technical writing. I was crushed to discover
       | that this was his first article (at this location).
        
         | jornhub wrote:
         | Thanks! What subjects do you care about?
        
           | vanderZwan wrote:
           | Not the person you replied to, but how about suffix and least
           | common prefix arrays? Once it clicks how they work they feel
           | quite simple, but can still be quite tricky to grok until
           | then.
        
           | kadoban wrote:
           | Segment trees are cool, if that's not too similar to Fenwick
           | for good content (they have some common uses).
           | 
           | Sqrt decomposition is a cool technique IMO too.
           | 
           | (I've been on a range-query kick recently).
        
       ___________________________________________________________________
       (page generated 2021-08-31 23:03 UTC)