3 ms·
Grokking Fenwick Trees
- vanderZwan 5y agoTo 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 5y agoI have no explanations but runnable code: https://www.nayuki.io/page/binary-indexed-tree https://www.nayuki.io/page/binary-indexed-tree
- Syzygies 5y agoThis is beautiful technical writing. I was crushed to discover that this was his first article (at this location).
- jornhub 5y agoThanks! What subjects do you care about?
- vanderZwan 5y agoNot 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 5y agoSegment 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).