I was reading this blog https://mirror.codeforces.com/blog/entry/100826. And suddenly it hit me that the technique is to build a number system such that each node has maximum two intervals half the size unlike Fenwick tree where subtraction by 1 on a power of two creates all full bits. Very innovative technique. However Fenwick decomposition is no less useful than the supplied skewed binary numbers decomposition.
Here we go.
Binary lifting can also be done in Fenwick nodes.
So far, the speed looks the same. However, query time complexity is log square in worst case like normal Fenwick range query.
https://cses.fi/problemset/task/1687/
Here's code using Fenwick decomposition for LCA
https://cses.fi/problemset/task/1688/
I am kinda fascinated by the former skewed decomposition where subtraction by 1 doesn't create more than two sub intervals. Thanks for reading.







