You could have invented Fenwick trees | Hacker News Reader

You could have invented Fenwick trees

cambridge.org

131 pointsmatt_d29 comments

I used them in my paper: https://arxiv.org/pdf/1701.07072

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.

So I guess I also agree with the title :)

I always feel warm inside when I hear of concepts in separate fields connecting in some way. Very cool

Fenwick trees are really interesting - I was implementing graph layout algorithms a few weeks ago, and it turns out they exactly answer the question of how many edges cross between two layers of a bipartite graph drawn with straight lines[1].

Or, in english, if you have a bunch of graph nodes and edges, and lay them out in straight lines horizontally and vertically in some fashion, with lines between them representing the edges, fenwick trees tell you how many of the lines that you draw run into each other [2].

This is normally an expensive thing to compute (the alternative is to use a standard line intersection calculation for every edge or something like this). However, it turns out fenwick trees directly encode and give you the answer.

So this is what ELK and Dagre and friends use to compute the number of edges that cross between layers as they do layout.

[1] see "Simple and Efficient Bilayer Cross Counting"

[2] In general, the graph is more visually pleasing to most people if you minimize the number of lines that cross. So most layout algorithms spend time rearranging the nodes to minimize edge crossings. It's NP-hard to make it optimal, so heuristics are used.

While it might be ok to use colloquially the term, "Fenwick trees" since it became a common name, calling them "a Fenwick's work" and not mentioning Ryabko is a clear misattribution.

Sure, by what I wrote above I meant more of a "Fenwick's paper" than "Fenwick's work" :)

That said, as far as I remember, I did not know about Ryabko. So while it might have been a misatribution, it's far from a clear one.

Did he publish it btw.? If so, do you have a reference?

All the references are on the wiki page: https://en.wikipedia.org/wiki/Fenwick_tree

Written by Brent Yorgey — I'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 "monad is like a burrito" tutorials.

[1] https://wiki.haskell.org/wikiupload/e/e9/Typeclassopedia.pdf

The wiki version thereof: https://wiki.haskell.org/Typeclassopedia.

Tangential to the algorithm itself, this is about naming:

> Fenwick trees, also known as binary indexed trees

Every time I read something like this, I'm reminded of https://willcrichton.net/notes/naming-conventions-that-need-... . "Fenwick tree" makes it seem like some unknown strange entity, while "binary indexed tree" immediately makes it a lot more accessible and gives you a better handle on the concept too.

I'm reminded of a town in New Mexico named after the railroad paymaster because everyone said "I'm going to see Gallup to get paid" -> "I'm going to Gallup to get paid" -> "I'm going to Gallup".

Short, memorable names will always dominate precise, descriptive ones.

Finding short, memorable, precise and descriptive names is why "naming things is hard".

Meh, I agree in spirit but in practice it’s quite hard to get enough unique names using descriptive terms. I also think there’s some benefit in learning history that comes from naming things after people.

In practice, the most it gets is people thinking "I guess some guy named Fenwick was involved somewhere along the way", if even that. I think there's a lot of benefit to learning the history of how things were discovered, but that should be done consciously by making it part of the teaching material. The names make barely any difference.

It's not trivial to come up with descriptive names, but the difficulty is often overstated because people underestimate its importance. The names don't have to be perfectly descriptive, we don't need twenty syllable names like organic chemical compounds, but every step taken towards making it descriptive helps a lot. The reality is that the names get chosen basically arbitrarily in journals or textbooks, with hardly any thought given to how it will affect generations of students, working professionals, and even future researchers in remembering the concept and looking it up in their mind among the hundreds or thousands of other things they've learnt.

I remember trying to memorise the implementation by following the e-maxx guides [1] (back then it was http://e-maxx.ru/) for use in competitive programming contests. They're so simple once you understand them, yet it's pretty easy to forget the details of the simple implementation if you haven't done it for a while.

[1]: https://cp-algorithms.com/data_structures/fenwick.html

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.

I am not sure that is something worth trying. In practice Fenwick trees are array-encoded, in memory they're just an array you index into. The reason B-trees are used is kind of because you can't do that with a dynamic binary tree.

They are array encoded, but you still will be jumping all over the array to do your operations. Putting multiple “nodes” at the same location will mean fewer jumps, and hence fewer cache misses.

That's what the Eytzinger ordering is for. Using 1-based indexing like the article, a single lookup will only hit the following nodes:

  1
  2 or 3 (let's assume 2)
  4 or 5 (let's assume 5)
  10 or 11

Remember these are all adjacent. So the nodes near the root stay in cache (regardless of whether a path through them in particular was taken), and the other nodes are in cache if you've recently looked up a similar key.

There won't be any further improvement from using a B-tree, which only scatters the memory further. (if anything, you might consider using a higher-base Eytzinger tree for SIMD reasons, but I've never actually seen anyone do this)

...So, could someone try putting one of these trees in place in... SQLite3 and see if it's any faster than it's use of B-Trees?.... Assuming this concept will work in C...

The discussion above is nuanced, but in short: the concept doesn't work for B-Trees or as a replacement for B-Trees at all. It's for a different thing where you have a fixed set of keys (especially 1 to n or something of that form).

The eytzinger layout cannot be used for anything dynamic. B-Trees are dynamic structures.

The discussion is about Fenwick trees.

Skip lists also have [statistically] sublinear times for insertions and range queries. Both are O(logn).

Fenwick trees seem to use much less memory while not being quite as general-purpose as skip lists.

There's several things like that you can accidentally re-invent. I re-invented the Trie, and Markov Chaining whilst at University. What I didn't do is give them a thorough and rigorous description in any kind of publication.

That's quite a big part of the difference, I think.

There’s also a huge difference between accidentally implementing an application of something vs spotting that it is a general principle

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'm finding that realizing solutions are novel and noteworthy is a lot harder.

When making my implementation, the math felt unintuitive. https://www.nayuki.io/page/binary-indexed-tree

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

It seems like all the algorithms post 2000 or so do not have that property as much. For example: https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf

Reply on news.ycombinator.com