[vh311]

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 :)

[guimplen]

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.

[vh311]

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?

[guimplen]

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

[cosmic_quanta]

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

[DannyBee]

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.