News for hackers. Stuff that matters.
Re:Grokking Fenwick Trees by vanderZwan on Tuesday August 31, 2021 @11:03AM (#28368985)
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?

Re:Grokking Fenwick Trees by nayuki on Tuesday August 31, 2021 @11:27AM (#28369254)
I have no explanations but runnable code: https://www.nayuki.io/page/binary-indexed-tree
Re:Grokking Fenwick Trees by Syzygies on Tuesday August 31, 2021 @11:54AM (#28369584)
This is beautiful technical writing. I was crushed to discover that this was his first article (at this location).
Re:Grokking Fenwick Trees by jornhub on Tuesday August 31, 2021 @11:57AM (#28369621)
Thanks! What subjects do you care about?
Re:Grokking Fenwick Trees by vanderZwan on Tuesday August 31, 2021 @12:30PM (#28370094)
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.
Re:Grokking Fenwick Trees by kadoban on Tuesday August 31, 2021 @06:32PM (#28374465)
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).