Length of Longest Increasing Subsequences (LIS) using Segment Tree

Approach

We will solve this problem using a segment tree. We can a max segment tree. A node of a segment tree will store two integers, the 1st one will be the length of LIS, and 2nd one will be the count of this length(i.e., how many LIS of the same size are present). 

The elements of the array are sorted in ascending order while retaining their original indexes. This can be done by a vector of pairs (by using a custom comparator). The second element of pairs is the original index of the element in the input array. 

The segment tree will be constructed in the following way:

Elements are inserted in the segment according to their order in the sorted array. Let j be the original index of ith element in the sorted array. Then ith element will be inserted at the jth leaf in the segment tree. 

Initially, we initialize the segment tree with {0, 0}. Let us assume that after processing i-1 elements, we are at ith element in the sorted array. Let its original index be j. Then ith element is inserted at the jth position in the segment tree with the 1st element as {maximum value of the length between 0 & j-1th leaf} + 1 (i.e., size of the LIS formed by elements smaller than it in the subarrar[0, j-1] and adding one for its inclusion). 

2nd element will be calculated according to the following cases:

(i) if the length of left child > length of the right child, then the value will be equal to the 2nd element of the left child as the LIS be of left child.

(ii) if the length of left child < length of the right child, then the value will be equal to the 2nd element of the right child as the LIS be of the right child.

(iii) If the left child’s length == length of the right child, then the value will be equal to the sum of the 2nd element of the left and right child.

After inserting all elements from the sorted array, the root node of the segment tree will contain {length of LIS of the whole array, count of this LIS}. Here count of the LIS will be our final answer.

Algorithm

1. Store all the input array elements in a separate vector of pairs with 1st value as element and 2nd as the index of this element in the input array.

2. Sort this vector of pairs according to the ascending order of elements value.

3. Iterate over all pairs in the sorted vector of pairs. Let ith elements value be i and its original index be j. Then, 

• Calculate the maximum length of LIS from (0 to j-1) index from the segment tree (calling query function).
• Update the jth leaf in the segment tree with value as 

{ (length of LIS from (0 to j-1) leaf) + 1, count this LIS }

4. Query the length of LIS of the whole array (interval 0 to n-1) and return the count of this length.

Program

#include <bits/stdc++.h>
using namespace std;

#define MAXSIZE 100000
#define pii pair<int, int>
#define F first
#define S second

/*-------------------- Auxillary function & objects for segment tree. BEGINS ----------------------------------------*/

// For storing the segment tree. (The root of the segment tree contains the length of the LIS and it's count).
vector<pii> tree;

/**
 * @brief Function for updating the segment tree. 
 * 
 * @param start left end of the Range/Interval which treeIdx represents.
 * @param end right end of the Range/Interval which treeIdx represents.
 * @param treeIdx Segment tree index in the array(Which represents the tree).
 * @param updateIdx Index to be updated.
 * @param length Length of LIS.
 * @param count Count of this LIS length.
 */
void update(int start, int end, int treeIdx, int updateIdx, int length, int count){

    /* If both intervals overlaps completely */
    if(start == end && start == updateIdx){
        /* Update the current tree node's length and count */
        tree[treeIdx].F = max(tree[treeIdx].F, length);
        tree[treeIdx].S = count;
        return;
    }

    /* If desired Index is completely outside the current Interval */
    if(updateIdx < start || end < updateIdx){
        /* Then ignore this subtree(do nothing) and return */
        return;
    }

    /* If intervals overlaps partially */
    int mid = (start + end) >> 1;

    /* Updating left subtree */
    update(start, mid, 2*treeIdx, updateIdx, length, count);
    /* Updating right subtree */
    update(mid+1, end, 2*treeIdx+1, updateIdx, length, count);

    /* If length of left & right child are equal */
    if(tree[2*treeIdx].F == tree[2*treeIdx+1].F){
        /* Then take the length same as left child, and update the count
        as the sum of left and right child */
        tree[treeIdx].F = tree[2*treeIdx].F;
        tree[treeIdx].S = tree[2*treeIdx].S + tree[2*treeIdx+1].S;
    }
    /* If length of left child is greater right child*/
    else if(tree[2*treeIdx].F > tree[2*treeIdx+1].F){
        /* Then take the length of Left child as it is greater. Count is also
        taken same as of the left child */
        tree[treeIdx] = tree[2*treeIdx];
    }
    /* If length of left child is less than right child */
    else if(tree[2*treeIdx].F > tree[2*treeIdx+1].F){
        /* Then take the length of Left child as it is greater. Count is also
        taken same as of the left child */
        tree[treeIdx] = tree[2*treeIdx+1];
    }
}

/**
 * @brief Function for finding the LIS and it's count in a given range.
 * 
 * @param start left end of the Range/Interval which treeIdx node represents.
 * @param end right end of the Range/Interval which treeIdx node represents.
 * @param treeIdx Index of current node in segment tree which represents the Interval [start, end].
 * @param queryStart left end of the queried Interval.
 * @param queryEnd right end of the queried Interval.
 * @return pair<int, int> 
 */
pii query(int start, int end, int treeIdx, int queryStart, int queryEnd){
    /* If both queried intervals is completely inside the CURRENT INTERVAL */
    if(queryStart <= start && end <= queryEnd){
        // Return length and count of current LIS 
        return tree[treeIdx];
    }

    /* If the intervals are completely DISJOINT */
    if(end < queryStart || queryEnd < start){
        return {INT_MIN, 0};
    }

    /* If both overlap partially */
    int mid = (start + end) >> 2;

    pii left = query(start, mid, 2*treeIdx, queryStart, queryEnd);
    pii right = query(mid+1, end, 2*treeIdx+1, queryStart, queryEnd);

    /* If length of left child is greater right child*/
    if(left.F > right.F)
        return left;

    /* If length of left child is less than right child */
    if(right.F > left.F)
        return right;
    
    /* If lenght of both children is equal then return count as 
    sum of left count and right count. */
    return {left.F, left.S + right.S};
}

/*-------------------- Auxillary function & objects for segment tree. ENDS ----------------------------------------*/


/* Comparator function for sorting array of pairs 
ACSENDING order of the 1st element and thereafter
in DESCENDING order of the 2nd element. */
bool customComparator(pii &a, pii &b){
    if(a.F == b.F)
        return a.S > b.S;
    return a.F < b.F;
}

/**
 * @brief Main function to solve the question
 * (finds the count of LIS in the given input array).
 * 
 * @param arr Input array.
 * @param n Length of Input array.
 * @return int 
 */
int solve(int arr[], int n){
    

    vector<pii> v(n);
    // v[i].F stores arr[i] element
    // v[i].S stores index of arr[i] in the original array.
    for(int i=0; i<n; i++)v[i].F = arr[i], v[i].S = i;

    /* Sort array of pairs in ASCENDING ORDER of elements value. */
    sort(v.begin(), v.end(), customComparator);

    for(int i=0; i<n; i++){
        
        int updateIdx = v[i].S;     

        if(updateIdx == 0){
            update(0, n-1, 1, updateIdx, 1, 1);
            continue;
        }

        // Find the LIS and it's count over the INTERVAL [0, updateIdx-1].
        pii tmp = query(0, n-1, 1, 0, updateIdx-1);

        // Updating the segment tree.
        update(0, n-1, 1, updateIdx, tmp.F+1, max(1, tmp.S));
    }

    pii finalAns = query(0, n-1, 1, 0, n-1);

    // return count of LIS of the array.
    return finalAns.S;
}


// Driver Function (It takes input and prints the final answer.)
int main(){
    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        int arr[n];

        tree.resize(4 * MAXSIZE + 1, {0, 0});

        for(int i=0; i<n; i++)cin >> arr[i];

        cout << solve(arr, n) << endl;
    }
    return 0;
}

INPUT

1
5
2 2 2 2 2
5
1 3 5 4 7

OUTPUT

5
2

Time Complexity

The time complexity of insertion & query in the segment tree is O(log N). Therefore the time complexity of the above approach is O(N  * log(N)). 

Space Complexity

The auxiliary space complexity of the program is O( N  ). 

Check out this array problem - Merge 2 Sorted Arrays

Check out this : Longest common subsequence

FAQs

1. What is a Segment Tree?
   A segment tree is a data structure that can solve range queries efficiently. 
    
2. What is segment tree used for?
   The segment tree is used for solving range queries. The time complexity of insertion & update is O(log N). Therefore range queries can be solved effectively using a segment tree. 
    
3. What is a Fenwick tree?
   A Fenwick tree or Binary indexed tree is a data structure used to efficiently update and calculate interval prefix sums in a linear array. 
    
4. What is the time complexity of updating & deleting in a Fenwick tree?
   The time complexity of update & delete is O(log N). 

Key Takeaways

Cheers if you reached here!! 

This article aimed to discuss an intriguing problem using the Segment Tree. Segment Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!