Longest increasing subsequence using a segment tree

Given an array of random non-negative numbers find the longest strictly increasing subsequence. You might have seen this solved with Dynamic Programming which has O(n^2) complexity, and another one which has O(n logn) complexity.

In this post I will discuss another simple way to implement the solution using segment trees.

Examples :

Input : 2 7 4 3 8
Output : 3
Explanation :
(2,7,8),(2,4,8),(2,3,8) are the longest strictly increasing
subsequences with length 3

Input : 1 4 5 4 7 9
Output : 5
Explanation :
(1,4,5,7,9) is the longest strictly increasing subsequence with length
5

First Let’s talk about what makes the DP approach slow

We have an array {2,7,4,3,8}

When we iterate through the array for the dynamic programming approach, for each number we want to know, amongst all the numbers, greater than this number, which ones has the longest chain length (and obviously that number has to be to the right of the current number)

for example for 4 only number to its right and bigger than it is 8 and has chain length of 1 (8 itself) so from 4 we can build a maximum length chain of 1 + 1 = 2

Now to find the best number we’ll have to iterate to the right of the current number which can take O(n) time and doing it for all n numbers we have O(n^2) time

Here comes Segment tree to the rescue!

If we want to find the best chain length amongst all numbers greater than a certain number then this problem is similar to find maximum in a range which can be done easily with segment trees!

Algorithm :

1. Create a Segment tree which maintains the maximum chain length possible for each number. If the maximum number is M. The segment tree has range from 0 to M.
2. Iterate from right to left of the array
   • For each element, find the longest chain length from “element + 1” to “M”, using the segment tree
   • The obtained value + 1, is the new chain length of this element
   • Update the segment tree accordingly
3. The maximum among all chain lengths obtained is the answer.

Some Doubts :

You are using one position for one element what about repeated elements?

You see, as we iterate from right to left, amongst similar elements, the element which is to the most left will always have the longest chain length, so we can overwrite similar elements while iterating. This can be easily seen why

As the element which is to the right has a certain chain length which can be directly appended to the left element, and furthermore the chain length might increase for this left element due to numbers present between the left and right element

How does this take care of the fact that numbers should be to the right of the current element?

As we move from right to left, only those elements which have appeared on the right side of the current element will be accounted for, the rest of them will have a default chain length value of 0.

Code :

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

int length(int ss, int se, int l, int r, int key, vector<int>& seg)
{ // find max chain length in l to r range
    if (max(l, ss) > min(r, se))
        return 0; // ss is start of segment, se is end of
                  // segment
    if (l <= ss && r >= se)
        return seg[key]; // key is actual position of value
                         // inside the seg vector
    int mid = ss + (se - ss) / 2;
    return max(length(ss, mid, l, r, key * 2 + 1, seg),
               length(mid + 1, se, l, r, key * 2 + 2, seg));
}

void update(int key, vector<int>& seg)
{ // update segment tree function
    if (key == 0)
        return; // if already at root node return
    int parent = (key - 1) / 2, child1 = parent * 2 + 1,child2 = child1 + 1;
    seg[parent] = max(seg[child1], seg[child2]); // update the parent
    update(parent, seg); // recurse
}

int longestIncreasingSubsequence(vector<int> arr)
{ // here M is supposed 1e5
    int n = arr.size(), N = 1e5 + 1, sz = 1, maxi = 0;
    // N is the total size (M+1 to account for 0) so seg
    // tree can support values 0,1,2 ... M
    // sz here is the segment tree size variable
    // maxi will store the longest chain encountered until
    // now
    while (sz < N) sz *= 2;
    vector<int> seg(2 * sz - 1); // segment tree creation
    for (int i = n - 1; i >= 0; --i) {
        auto temp = length(0, sz - 1, arr[i] + 1, N - 1, 0, seg);
        // find the longest chain among elements arr[i] + 1
        // and the maximum element. arr[i] + 1 because the
        // element has to be strictly increasing
        seg[sz - 1 + arr[i]] = temp + 1; // update the value
        maxi = max(maxi, seg[sz - 1 + arr[i]]); // update maxi
        update(sz - 1 + arr[i], seg); 
        // update segment tree with the new value
    }
    return maxi;
}

int main()
{
    vector<int> v = { 2, 7, 4, 3, 8 };
    cout << longestIncreasingSubsequence(v);
}

Time Complexity : Since we iterate through the entire array once and use segment tree to find and update values, we have O(logn) operations executed O(n) times, therefore leading to time complexity of O(n logn)

There are lots of places where you can test this code out or write it yourself, one of them is https://www.hackerrank.com/challenges/longest-increasing-subsequent/

Bonus: Here you can see the segment trees builds on the maximum value of the elements so it works when the input is given something like

1 <= arr[i] <= 1e5

But what if the elements’ value is something larger? let’s say in ranges 1 <= arr[i] <= 1e15

Obviously in this case, you can’t build segment tree on the maximum value, but this method can still be used, can you guess how?

Hint: Just sort the input and use the position of the elements to update and use the segment tree. We are going to overwrite duplicate elements anyway so you can use set to first clear all duplicate elements and then assign position values to each element. 

Then we iterate right to left in original array and in each query we  find the maximum value in  range pos[current_element] + 1 to max_pos

and update the value at this position accordingly.