This blog came about because of some pretty random events.
A while back ponysalvaje explained me how the Fenwick Tree works and some cool tricks you can do with it.
Some time later, I saw this blog. As soon as I read the first paragraph, I stopped and tried to invent such a data structure myself. I thought of storing jumps of distance $$$LSB(depth_u)$$$. This works, but the ancestor queries are actually $$$O(\log(N)^{2})$$$ in the worst case. Adding new leaf requires an ancestor query, but it happens to actually be $$$O(\log(N))$$$ because of some happy accidents.
This made me realize that you can compute any range query on an FT, not just prefixes (but in $$$O(\log(N)^{2})$$$ time). Because of this, I wrote this other blog.
Then, I read the original blog and thought that the idea presented in it can also be used to compute range queries and updates. (I didn't prove it but it seems obvious that each position in the array is covered by, at most, $$$\log(N)$$$ ranges)
