You are given an array of length N. You have to find the longest increasing subsequence (LIS) from the given array. We will try to solve this problem using Fenwick Tree which will take O(N logN) time complexity. The brute force approach will take O(2^N) time complexity.

Given array :

arr = {9,6,2,3,7,5,8,4}

Our output will be 4, as {2,3,5,8} is the longest increasing subsequence.

Prerequisite to understand this problem is knowledge about Fenwick Tree. So, before starting this problem, have a quick overview of Fenwick Tree or Binary Indexed Tree.

So as you know, The basic idea behind Fenwick tree is that since any integer can be represented as sum of powers of 2, we can represent cumulative frequencies as sum of non-overlapping sub-frequencies.

• To get the index of next node in Fenwick Tree, we use :> index -= index & (-index)
• To get the index of previous node in Fenwick Tree, we use :> index += index & (-index)

Now, after reading about Fenwick tree you must have got a decent knowledge about it, and how they are formed and how they can be used to solve various problems.

Here, the problem we are trying to solve is Given an array of size n, we have to find the length of Longest increasing subsequence in the given array using Fenwick tree or Binary indexed tree(BIT).

As we will be using fenwick tree, the time complexity of our solution would be O(N log(N)) where N is number of elements in given array.

Solution

To solve this problem, we would first create a fenwick tree as an array of length N+1, as the 0'th position works as a root. Then we will map our array elements according to their ranks in given array.

For example:
Given array : [3, 5, 1]
So our mapped array would be : [2, 3, 1] as in given array, 1 is smallest element so its rank would be 1, rank 2 will be given to element 3 and so on.

This data mapping will make our data comparison easy and it would be simpler to fill our fenwick tree.

After mapping we would start filling our fenwick tree according to the data present in mapped array and data filled in our fenwick tree.

At end, we would get our fenwick tree in which each element will be showing the length of longest incresing subsequence till that element.

Pseudocode

1. Sort the given array and create a dictionary with keys as array's element and value as its rank in sorted array.
2. Update the array with ranks assigned to respective elements.
3. Create a fenwick tree array of size n+1 and elements as 0.
4. Start traversing the array and for each index recieved from array, fill that position in fenwick tree array with the (maximum lenght formed till that index) + 1.
5. Repeat this for whole array.
6. Return the lenght of longest increasing subsequence from filled fenwick tree.

Implementation in Python

Following is our Python implementation of solving the Longest Increasing Subsequence problem using Fenwick Tree:

# Function that returns the longest increasing subsequence
def answer(arr):
    n = len(arr)

    ##### INITIALISING FENWICK TREE #####
    fenwick_tree = [0]*(n+1)

    ########## MAPPING DATA ACCORDING TO THEIR RANK IN LIST ###########
    sorted_arr = sorted(arr) # Sorting data

    # Creating dictionary
    dictionary = {}
    for i in range(n):
        dictionary[sorted_arr[i]] = i+1

    # Mapping arr data
    for i in range(n):
        arr[i] = dictionary[arr[i]]

    ##*************************************************##

    ##################### FILLING OUR FENWICK TREE #####################
    for i in range(n):

        # Taking rank of elements as index of tree
        index = arr[i]

        # Asking for maximum length in fenwick tree till this index
        x = query(fenwick_tree, index-1)

        # Incrementing length
        val = x+1

        # Traversing in fenwick tree from parent to child
        while(index<=n):

            # Filling length at respective indexes
            fenwick_tree[index] = max(val, fenwick_tree[index])

            # Getting index of next node in fenwick tree
            index += index & (-index)

    ##************************************************##

    # Returning answer as query
    return query(fenwick_tree, n)
    
######### FUNCTION THAT CHECKS FOR MAX LENGTH TILL i'th INDEX ########
def query(f_tree, index):
    ans = 0

    # Traversing in fenwick tree from child to parent
    while index>0:
        ans = max(f_tree[index],ans)

        # Getting index of previous node in fenwick tree
        index -= index & (-index)
    return ans

###########################################

# Tesing our code
arr = [6, 5, 1, 12, 2, 4, 9, 8]
ans = answer(arr)
print(ans)

Worflow of Solution

1. Suppose we are given the array as [6, 5, 1, 12, 2, 4, 9, 8] .
2. We map the elements of given array according to their ranks, so we update or array to : [5, 4, 1, 8, 2, 3, 7, 6].
3. Now, we start traversing our mapped array and we get 5 as our first element, remember that this 5 represents the rank of the element present at 0'th position in our original array which was 6.
4. So, we ask our query fuction about the maximum length we found till 4'th position in fenwick_tree. As all elements or fenwick tree are 0 now, we get our x as 0, so we increment it to 1 and fill it in our fenwick_tree array, to all the positions we get as our next node in fenwick tree, through the formula : index -= index & (-index) which you read about earlier.
5. You would have read about this formula in the article mentioned above.
6. So, now our fenwick_tree looks as : [0, 0, 0, 0, 0, 1, 1, 0, 1].
7. We repeat this for all the elements of mapped array, and we will get the fenwick_tree in end as : [0, 1, 2, 3, 3, 1, 4, 4, 4]
8. So, this fenwick_tree shows the maximum length of increasing subsequence at each element in given array.
9. At end, we return the length of longest incresing subsequence in given array.

Complexity

As we traverse the whole array, and for each element we traverse the parent to child positions in fenwick_tree array, so we get the time complexity as O(nlogn), where n is size of given array.

With this article at OpenGenus, you must have a complete idea of solving this problem of Longest Increasing Subsequence using Fenwick Tree. Enjoy.