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?
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.
6 comments
[ 150 ms ] story [ 943 ms ] threadI 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?
Sqrt decomposition is a cool technique IMO too.
(I've been on a range-query kick recently).