There are a number of blogs which describe the implementation of ordered_set using Fenwick trees.
Is there any way to implement fenwick tree struct using ordered_set? And could that be extended to the 2D case?
Motivation: I really suck at fenwick trees, and always get around by segtree templates... So, I'm trying to find a way to solve when I don't have access to templates... :(
In my opinion using ordered sets to implement Fenwick trees defeats the whole purpose of having Fenwick trees from the start (which is having a lightweight PURQ data structure with lower memory usage and constant).
If your purpose is to have a PURQ data structure without using any templates where you just need to utilize existing C++ PBDS, this blog might help, although it looks like implementing a Fenwick tree alone would be much shorter.
Correct.
There are two things which we both call data structures — interface and implementation. Both Fenwick tree and
ordered_setare implementations.ordered_setis an implementation of a binary search tree, Fenwick tree is an implementation of a data structure for single point update (usually undoable or idempotent) and prefix sum query. Thereforeordered_setis much more powerful than the Fenwick tree, but the latter is much faster and lighter.If you need Fenwick tree then just find an implementation in the Internet, they all are short and easy to write and memorize. If you need a binary search tree then look for a
pb_dsblog on Codeforces or Google regardingordered_set.Thank you