CODEWITHSUNDEEP
arraysalgorithmoptimizationtreebinary-indexed-tree
Vishal Jangid
Vishal Jangid

Reputation: 418

How to Use Binary Indexed Tree for Counting Reverse Pairs in an Array?

I'm currently attempting to solve the Reverse Pairs problem on LeetCode, where I need to count the number of reverse pairs (i, j) in an array nums such that 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

I've been exploring the use of a Binary Indexed Tree (BIT) or Fenwick Tree for this problem, as I understand it's efficient for handling cumulative frequency tasks. However, I'm having difficulty grasping how exactly a BIT can be applied here, especially in conjunction with the technique of data discretization which I learned about from this Medium article.

My specific questions are:

  1. How does BIT help in counting reverse pairs? I'm unable to visualize how querying and updating a BIT can be used to effectively count the reverse pairs given the nums[i] > 2 * nums[j] condition.

  2. Application of Data Discretization: How does the process of discretizing data play into the use of BIT for this specific problem?

Any insights or examples that could help clarify these points would be greatly appreciated. I'm looking for an explanation or a conceptual overview rather than specific code.

Upvotes: 1

Views: 225

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59263

A Fenwick tree solves a lot of these 2-dimensional query problems.

  1. Make a list of the array indexes, sorted by the corresponding value in descending order.

  2. Using a "two pointer" technique, iterate j through this list: for j in index list, and for each j, increment i past all indexes such that nums[i] > 2 * nums[j]

  3. Add each i to the Fenwick tree as you increment past it.

  4. For each j, use the Fenwick tree to get the number of indexes less than j, and add to a total.

In this algorithm, the iteration order (descending by value) for the two-pointer iteration implements the value constraint, while the Fenwick tree implements the index ordering constraint.

Here's an implementation in python, using the fenwick tree code from here: Simpler Alternatives to Fenwick Trees

def reversePairs(nums):
    # indexes in descending value order
    indexes = [x for x in range(len(nums))]
    indexes.sort(key=lambda i: -nums[i])

    #empty fenwick tree
    ft = [0]*len(nums)

    #two-pointer iteration
    total = 0
    ii = 0
    for j in indexes:
        while nums[indexes[ii]] > 2*nums[j]:
            i = indexes[ii]
            ii += 1
            # put i in the fenwick tree
            i += 1
            while i <= len(ft):
                ft[i-1] += 1
                i += i&-i
        # how many indexes < j are in the tree?
        n = j
        while n > 0:
            total += ft[n-1]
            n &= n-1

    return total

You could also implement it the other way, iterating order and checking value. In this case, though, in order to limit the size of the Fenwick tree, you would need to perform some transformation of the values to limit their range. That would be a little complicated.

Upvotes: 1

Related Questions