roycf123's blog

By roycf123, history, 10 months ago, In English

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... :(

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Correct.

    There are two things which we both call data structures — interface and implementation. Both Fenwick tree and ordered_set are implementations. ordered_set is 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. Therefore ordered_set is 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_ds blog on Codeforces or Google regarding ordered_set.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you