Implementing an ordered set(pbds) using Fenwick trees

Question:

We're asked to implement an ordered set.

Here are the operations :

1) insertion into set in logn

2) deletion from the set in logn

3) Finding the order of an element in logn. Order of an element is defined as the number of elements already present in the set , that are less than or equal to the given number.

(Note: This question has appeared in a SPRINKLR interview, infact appeared in two consecutive rounds of the same interview. Here's the link )

Objective:

We will approach this as an interview question rather than an online challenge. Thus we would focus on an implementation that is readable, easy to code and easy to explain.

Analysis:

1) Simple but inefficient approaches:

• We can use an array, which we sort after every updation ,deletion. Thus we can find order of an element in logN using binary search.

Time-complexity: insertion (NlogN), deletion(NlogN), order(logN)

• We can use a list , which allows updation and deletion in O(N). But now even finding order takes O(N)

Time-complexity: O(N) for all three operations.

2) Efficient but hard to implement:

We can solve this using a Segment tree (given Ai<1e6) which is hard and tedious to code in an interview setup. Also if they tighten the constraints to (Ai<1e18), we would need a dynamic segment tree, which is a nightmare to code(in an interview setup)

3) Using Fenwick Trees:

We would use this method to solve this problem for both loose and tight constraints in less than 10 lines of code( No typos here, 20 -25 lines including library imports and driver code).

Pre-Requisites:

The only pre-requisite is to know how to implement a Fenwick tree.

If you don't know how to implement one, then here are the resources:

1) In Hindi by Luv . (no typos again)

2) A codeforces blog in english. Link

Implementation:

1) The idea is simple for loose constraints. i.e (N<1e5 and Ai<1e6). We maintain a frequency array, that stores the frequency for every value of Ai.

• Now insertion is equivalent to increasing frequency of Ai in the frequency array by 1.
• Deletion is equivalent to decreasing frequency of Ai in the frequency array by 1.
• Finding order is equivalent to the range sum (0,Ai) over the frequency array.

Now if we build a Fenwick Tree over the frequency array, we can perform all three operations in logn.

Here is the implementation.

2) Now comes the harder part. i.e if (N<1e5 and Ai<1e18). The issue here is that we can't build a frequency array of that size. The only known standard solution is to use a dynamic segment tree which again is a nightmare to code. But there is another elegant solution to this.

We will change the underlying data structure of the fenwick tree from an array to a map.

Proof for space:

You can see that every query can only influence or create 32(logn) nodes at max in the map. So the space complexity would be 32*N.

Here is the implementation.

Extras:

If you are in a contest, you don't actually have to apply all this. There is a library called pbds that implements this for you. Link.