You could have invented Fenwick trees

I used them in my paper: <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1701.07072" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1701.07072</a><p>They appear quite naturally in the fermion-qubit mappings we looked at and I worked the data structure out at the time and only then found out about Fenwick’s work.<p>So I guess I also agree with the title :)

Written by Brent Yorgey — I&#x27;ll definitely give it a read when I have time. When I was learning Haskell, I found his Typeclassopedia [1] to be the best explanation of Monads, Monoids, Applicative and such. His pedagogical approach was delightful in contrast to all the &quot;monad is like a burrito&quot; tutorials.<p>[1] <a href="https:&#x2F;&#x2F;wiki.haskell.org&#x2F;wikiupload&#x2F;e&#x2F;e9&#x2F;Typeclassopedia.pdf" rel="nofollow">https:&#x2F;&#x2F;wiki.haskell.org&#x2F;wikiupload&#x2F;e&#x2F;e9&#x2F;Typeclassopedia.pdf</a>

Tangential to the algorithm itself, this is about naming:<p>&gt; Fenwick trees, also known as binary indexed trees<p>Every time I read something like this, I&#x27;m reminded of <a href="https:&#x2F;&#x2F;willcrichton.net&#x2F;notes&#x2F;naming-conventions-that-need-to-die&#x2F;" rel="nofollow">https:&#x2F;&#x2F;willcrichton.net&#x2F;notes&#x2F;naming-conventions-that-need-...</a> . &quot;Fenwick tree&quot; makes it seem like some unknown strange entity, while &quot;binary indexed tree&quot; immediately makes it a lot more accessible and gives you a better handle on the concept too.

I remember trying to memorise the implementation by following the e-maxx guides [1] (back then it was <a href="http:&#x2F;&#x2F;e-maxx.ru&#x2F;" rel="nofollow">http:&#x2F;&#x2F;e-maxx.ru&#x2F;</a>) for use in competitive programming contests. They&#x27;re so simple once you understand them, yet it&#x27;s pretty easy to forget the details of the simple implementation if you haven&#x27;t done it for a while.<p>[1]: <a href="https:&#x2F;&#x2F;cp-algorithms.com&#x2F;data_structures&#x2F;fenwick.html" rel="nofollow">https:&#x2F;&#x2F;cp-algorithms.com&#x2F;data_structures&#x2F;fenwick.html</a>

In the same way that B-trees have emerged as a more cache friendly version of binary trees, it seems like you could create a Fenwick tree that stores multiple “children” at the same location. It would probably be less algorithmically beautiful, but would be faster over all.

Skip lists also have [statistically] sublinear times for insertions and range queries. Both are O(logn).<p>Fenwick trees seem to use much less memory while not being quite as general-purpose as skip lists.

There&#x27;s several things like that you can accidentally re-invent. I re-invented the Trie, and Markov Chaining whilst at University. What I didn&#x27;t do is give them a thorough and rigorous description in any kind of publication.<p>That&#x27;s quite a big part of the difference, I think.

Totally agree with the title. I discovered Fenwick trees as part of solving a Project Euler, then from the problem forum I found out someone had invented this in the 90s and other people had imagined it much earlier.

I used to think inventing new things was the hard part. Now I&#x27;m finding that realizing solutions are novel and noteworthy is a lot harder.

When making my implementation, the math felt unintuitive. <a href="https:&#x2F;&#x2F;www.nayuki.io&#x2F;page&#x2F;binary-indexed-tree" rel="nofollow">https:&#x2F;&#x2F;www.nayuki.io&#x2F;page&#x2F;binary-indexed-tree</a>

This is the beauty of some of the best algorithms. It always feels like &quot;I could have written that paper&quot;