Horje
Length of Longest Increasing Subsequences (LIS) using Segment Tree

Given an array arr[] of size N, the task is to count the number of longest increasing subsequences present in the given array.

Example:

Input: arr[] = {2, 2, 2, 2, 2}
Output: 5
Explanation: The length of the longest increasing subsequence is 1, i.e. {2}. Therefore, count of longest increasing subsequences of length 1 is 5. 
 

Input: arr[] = {1, 3, 5, 4, 7}
Output: 2
Explanation: The length of the longest increasing subsequence is 4, and there are 2 longest increasing subsequences of length 4, i.e. {1, 3, 4, 7} and {1, 3, 5, 7}.

Approach: An approach to the given problem has been already discussed using dynamic programming in this article. 
This article suggests a different approach using segment trees. Follow the below steps to solve the given problem:

  • Initialise the segment tree as an array of pairs initially containing pairs of (0, 0), where the 1st element represents the length of LIS and 2nd element represents the count of LIS of current length.
  • The 1st element of the segment tree can be calculated similarly to the approach discussed in this article.
  • The 2nd element of the segment tree can be calculated using the following steps:
    • If cases where the length of left child > length of right child, the parent node becomes equal to the left child as LIS will that be of the left child.
    • If cases where the length of left child < length of right child, the parent node becomes equal to the right child as LIS will that be of the right child.
    • If cases where the length of left child = length of right child, the parent node becomes equal to the sum of the count of LIS of the left child and the right child.
  • The required answer is the 2nd element of the root of the segment tree.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define M 100000
 
// Stores the Segment tree
vector<pair<int, int> > tree(4 * M + 1);
 
// Function to update Segment tree, the root
// of which contains the length of the LIS
void update_tree(int start, int end,
                 int update_idx, int length_t,
                 int count_c, int idx)
{
    // If the intervals
    // are overlapping completely
    if (start == end
        && start == update_idx) {
        tree[idx].first
            = max(tree[idx].first, length_t);
        tree[idx].second = count_c;
        return;
    }
 
    // If intervals are not overlapping
    if (update_idx < start
        || end < update_idx) {
        return;
    }
 
    // If intervals are partially overlapping
    int mid = (start + end) / 2;
 
    update_tree(start, mid, update_idx,
                length_t, count_c,
                2 * idx);
    update_tree(mid + 1, end, update_idx,
                length_t, count_c,
                2 * idx + 1);
 
    // If length_t of left and
    // right child are equal
    if (tree[2 * idx].first
        == tree[2 * idx + 1].first) {
        tree[idx].first
            = tree[2 * idx].first;
        tree[idx].second
            = tree[2 * idx].second
              + tree[2 * idx + 1].second;
    }
 
    // If length_t of left > length_t right child
    else if (tree[2 * idx].first
             > tree[2 * idx + 1].first) {
        tree[idx] = tree[2 * idx];
    }
 
    // If length_t of left < length_t right child
    else {
        tree[idx] = tree[2 * idx + 1];
    }
}
 
// Function to find the LIS length
// and count in the given range
pair<int, int> query(int start, int end,
                     int query_start,
                     int query_end, int idx)
{
    // If the intervals
    // are overlapping completely
    if (query_start <= start
        && end <= query_end) {
        return tree[idx];
    }
 
    // If intervals are not overlapping
    pair<int, int> temp({ INT32_MIN, 0 });
    if (end < query_start
        || query_end < start) {
        return temp;
    }
 
    // If intervals are partially overlapping
    int mid = (start + end) / 2;
    auto left_child
        = query(start, mid, query_start,
                query_end, 2 * idx);
    auto right_child
        = query(mid + 1, end, query_start,
                query_end, 2 * idx + 1);
 
    // If length_t of left child is greater
    // than length_t of right child
    if (left_child.first > right_child.first) {
        return left_child;
    }
 
    // If length_t of right child is
    // greater than length_t of left child
    if (right_child.first > left_child.first) {
        return right_child;
    }
 
    // If length_t of left
    // and right child are equal
    // return there sum
    return make_pair(left_child.first,
                     left_child.second
                         + right_child.second);
}
 
// Comparator function to sort an array of pairs
// in increasing order of their 1st element and
// thereafter in decreasing order of the 2nd
bool comp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first < b.first;
}
 
// Function to find count
// of LIS in the given array
int countLIS(int arr[], int n)
{
    // Generating value-index pair array
    vector<pair<int, int> > pair_array(n);
    for (int i = 0; i < n; i++) {
        pair_array[i].first = arr[i];
        pair_array[i].second = i;
    }
 
    // Sort array of pairs with increasing order
    // of value and decreasing order of index
    sort(pair_array.begin(),
         pair_array.end(), comp);
 
    // Traverse the array
    // and perform query updates
    for (int i = 0; i < n; i++) {
 
        int update_idx = pair_array[i].second;
 
        // If update index is the 1st index
        if (update_idx == 0) {
            update_tree(0, n - 1, 0, 1, 1, 1);
            continue;
        }
 
        // Query over the interval [0, update_idx -1]
        pair<int, int> temp
            = query(0, n - 1, 0,
                    update_idx - 1, 1);
 
        // Update the segment tree
        update_tree(0, n - 1, update_idx,
                    temp.first + 1,
                    max(1, temp.second), 1);
    }
 
    // Stores the final answer
    pair<int, int> ans
        = query(0, n - 1, 0, n - 1, 1);
 
    // Return answer
    return ans.second;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 3, 5, 4, 7 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << countLIS(arr, n);
 
    return 0;
}

Java

import java.util.*;
import java.io.*;
 
// Java program for the above approach
public class GFG{
 
    public static int M = 100000;
 
    // Stores the Segment tree
    public static ArrayList<ArrayList<Integer>> tree =
      new ArrayList<ArrayList<Integer>>();
 
    // Function to update Segment tree, the root
    // of which contains the length of the LIS
    public static void update_tree(int start, int end,
                                   int update_idx, int length_t,
                                   int count_c, int idx)
    {
        // If the intervals
        // are overlapping completely
        if (start == end && start == update_idx) {
            tree.get(idx).set(0, Math.max(tree.get(idx).get(0), length_t));
            tree.get(idx).set(1, count_c);
            return;
        }
 
        // If intervals are not overlapping
        if (update_idx < start || end < update_idx) {
            return;
        }
 
        // If intervals are partially overlapping
        int mid = (start + end) / 2;
 
        update_tree(start, mid, update_idx,
                    length_t, count_c, 2 * idx);
        update_tree(mid + 1, end, update_idx,
                    length_t, count_c, 2 * idx + 1);
 
        // If length_t of left and
        // right child are equal
        if (tree.get(2 * idx).get(0) == tree.get(2 * idx + 1).get(0)) {
            tree.set(idx, new ArrayList<Integer>(
                List.of(tree.get(2 * idx).get(0),
                        tree.get(2 * idx).get(1) +
                        tree.get(2 * idx + 1).get(1))
            ));
        }
 
        // If length_t of left > length_t right child
        else if (tree.get(2 * idx).get(0) > tree.get(2 * idx + 1).get(0)) {
            tree.set(idx, new ArrayList<Integer>(
                List.of(tree.get(2 * idx).get(0), tree.get(2 * idx).get(1))
            ));
        }
 
        // If length_t of left < length_t right child
        else {
            tree.set(idx, new ArrayList<Integer>(
                List.of(tree.get(2 * idx + 1).get(0), tree.get(2 * idx + 1).get(1))
            ));
        }
    }
 
    // Function to find the LIS length
    // and count in the given range
    public static ArrayList<Integer> query(int start, int end,
                                           int query_start,
                                           int query_end, int idx)
    {
        // If the intervals
        // are overlapping completely
        if (query_start <= start && end <= query_end) {
            return new ArrayList<Integer>(tree.get(idx));
        }
 
        // If intervals are not overlapping
        ArrayList<Integer> temp = new ArrayList<Integer>(
            List.of(Integer.MIN_VALUE, 0 )
        );
 
        if (end < query_start || query_end < start) {
            return new ArrayList<Integer>(temp);
        }
 
        // If intervals are partially overlapping
        int mid = (start + end) / 2;
        ArrayList<Integer> left_child = query(start, mid,
                                              query_start,
                                              query_end, 2 * idx);
        ArrayList<Integer> right_child = query(mid + 1, end,
                                               query_start,
                                               query_end, 2 * idx + 1);
 
        // If length_t of left child is greater
        // than length_t of right child
        if (left_child.get(0) > right_child.get(0)) {
            return new ArrayList<Integer>(left_child);
        }
 
        // If length_t of right child is
        // greater than length_t of left child
        if (right_child.get(0) > left_child.get(0)) {
            return new ArrayList<Integer>(right_child);
        }
 
        // If length_t of left
        // and right child are equal
        // return there sum
        return new ArrayList<Integer>(
            List.of(
                left_child.get(0),
                left_child.get(1) + right_child.get(1)
            )
        );
    }
 
    // Function to find count
    // of LIS in the given array
    public static int countLIS(int arr[], int n)
    {
        // Generating value-index pair array
        ArrayList<ArrayList<Integer>> pair_array = new ArrayList<ArrayList<Integer>>();
 
        for(int i = 0 ; i < n ; i++){
            pair_array.add(new ArrayList<Integer>(
                List.of(arr[i], i)
            ));
        }
 
        // Sort array of pairs with increasing order
        // of value and decreasing order of index
        Collections.sort(pair_array, new comp());
 
        // Traverse the array
        // and perform query updates
        for (int i = 0 ; i < n ; i++) {
 
            int update_idx = pair_array.get(i).get(1);
 
            // If update index is the 1st index
            if (update_idx == 0) {
                update_tree(0, n - 1, 0, 1, 1, 1);
                continue;
            }
 
            // Query over the interval [0, update_idx -1]
            ArrayList<Integer> temp = query(0, n - 1, 0,
                                            update_idx - 1, 1);
 
            // Update the segment tree
            update_tree(0, n - 1, update_idx, temp.get(0) + 1,
                        Math.max(1, temp.get(1)), 1);
        }
 
        // Stores the final answer
        ArrayList<Integer> ans = query(0, n - 1, 0, n - 1, 1);
 
        // Return answer
        return ans.get(1);
    }
 
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 3, 5, 4, 7 };
        int n = arr.length;
 
        for(int i = 0 ; i < 4*M + 1 ; i++){
            tree.add(new ArrayList<Integer>(
                List.of(Integer.MIN_VALUE,0)
            ));
        }
 
        System.out.println(countLIS(arr, n));
    }
}
 
 // Comparator function to sort an array of pairs
// in increasing order of their 1st element and
// thereafter in decreasing order of the 2nd
public class comp implements Comparator<ArrayList<Integer>>{
    public int compare(ArrayList<Integer> a, ArrayList<Integer> b)
    {
        if (a.get(0).equals(b.get(0))) {
            return b.get(1).compareTo(a.get(1));
        }
        return a.get(0).compareTo(b.get(0));
    }
}
 
// This code is contributed by subhamgoyal2014.

C#

// Finding the Longest Increasing Subsequence using
// Segment Tree
 
using System;
 
class SegmentTree {
    private int[] tree; // The segment tree array
 
    // Constructor that initializes the segment tree
    public SegmentTree(int size)
    {
        // Determine the height of the tree
        int height = (int)Math.Ceiling(Math.Log(size, 2));
        // Determine the maximum size of the tree array
        int maxSize = 2 * (int)Math.Pow(2, height) - 1;
        // Create the tree array
        tree = new int[maxSize];
    }
 
    // Method that builds the segment tree from an array
    public void BuildTree(int[] arr, int pos, int low,
                          int high)
    {
        // If the segment has only one element, set the
        // corresponding value in the tree
        if (low == high) {
            tree[pos] = arr[low];
            return;
        }
 
        // Determine the middle index of the segment
        int mid = (low + high) / 2;
        // Recursively build the left subtree
        BuildTree(arr, 2 * pos + 1, low, mid);
        // Recursively build the right subtree
        BuildTree(arr, 2 * pos + 2, mid + 1, high);
        // Set the value of the current node to the maximum
        // value of its children
        tree[pos] = Math.Max(tree[2 * pos + 1],
                             tree[2 * pos + 2]);
    }
 
    // Method that returns the maximum value in a given
    // range
    public int Query(int pos, int low, int high, int start,
                     int end)
    {
        // If the given range is fully contained in the
        // current segment, return the corresponding value
        // in the tree
        if (start <= low && end >= high) {
            return tree[pos];
        }
 
        // If the given range does not overlap with the
        // current segment, return the minimum possible
        // value
        if (start > high || end < low) {
            return int.MinValue;
        }
 
        // Determine the middle index of the segment
        int mid = (low + high) / 2;
        // Recursively query the left subtree
        int left = Query(2 * pos + 1, low, mid, start, end);
        // Recursively query the right subtree
        int right
            = Query(2 * pos + 2, mid + 1, high, start, end);
        // Return the maximum value of the two subtrees
        return Math.Max(left, right);
    }
}
 
class LIS {
    // Method that returns the length of the longest
    // increasing subsequence in an array
    public static int GetLISLength(int[] arr)
    {
        int n = arr.Length;
 
        // Create a sorted copy of the array
        int[] sortedArr = new int[n];
        Array.Copy(arr, sortedArr, n);
        Array.Sort(sortedArr);
 
        // Create a map that maps the elements of the
        // original array to their indices in the sorted
        // array
        int[] indexMap = new int[n];
        for (int i = 0; i < n; i++) {
            indexMap[Array.IndexOf(sortedArr, arr[i])] = i;
        }
 
        // Create a segment tree to store the dynamic
        // programming values
        SegmentTree tree = new SegmentTree(n);
        // Build the initial tree with all values set to
        // zero
        tree.BuildTree(new int[n], 0, 0, n - 1);
 
        // Create an array to store the dynamic programming
        // values
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int prevMax = tree.Query(0, 0, n - 1, 0,
                                     indexMap[i] - 1);
            dp[i] = prevMax + 1;
            tree.BuildTree(dp, 0, 0, n - 1);
        }
 
        // Searching for the maximum value of longest
        // increasing subsequence
        int maxLIS = 0;
        for (int i = 0; i < n; i++) {
            maxLIS = Math.Max(maxLIS, dp[i]);
        }
 
        // Return the maximum value of longest increasing
        // subsequence
        return maxLIS;
    }
}
 
// Driver code
class Program {
    static void Main(string[] args)
    {
        int[] arr = { 1, 3, 5, 4, 7 };
        Console.WriteLine(LIS.GetLISLength(arr));
    }
}

Javascript

<script>
// Javascript implementation of the above approach
 
 
let M = 100000
 
// Stores the Segment tree
let tree = new Array(4 * M + 1).fill(0).map(() => []);
 
// Function to update Segment tree, the root
// of which contains the length of the LIS
function update_tree(start, end, update_idx, length_t, count_c, idx) {
  // If the intervals
  // are overlapping completely
  if (start == end
    && start == update_idx) {
    tree[idx][0]
      = Math.max(tree[idx][0], length_t);
    tree[idx][1] = count_c;
    return;
  }
 
  // If intervals are not overlapping
  if (update_idx < start
    || end < update_idx) {
    return;
  }
 
  // If intervals are partially overlapping
  let mid = Math.floor((start + end) / 2);
 
  update_tree(start, mid, update_idx,
    length_t, count_c,
    2 * idx);
  update_tree(mid + 1, end, update_idx,
    length_t, count_c,
    2 * idx + 1);
 
  // If length_t of left and
  // right child are equal
  if (tree[2 * idx][0]
    == tree[2 * idx + 1][0]) {
    tree[idx][0]
      = tree[2 * idx][0];
    tree[idx][1]
      = tree[2 * idx][1]
      + tree[2 * idx + 1][1];
  }
 
  // If length_t of left > length_t right child
  else if (tree[2 * idx][0]
    > tree[2 * idx + 1][0]) {
    tree[idx] = tree[2 * idx];
  }
 
  // If length_t of left < length_t right child
  else {
    tree[idx] = tree[2 * idx + 1];
  }
}
 
// Function to find the LIS length
// and count in the given range
function query(start, end, query_start, query_end, idx) {
  // If the intervals
  // are overlapping completely
  if (query_start <= start
    && end <= query_end) {
    return tree[idx];
  }
 
  // If intervals are not overlapping
  let temp = [Number.MIN_SAFE_INTEGER, 0];
  if (end < query_start
    || query_end < start) {
    return temp;
  }
 
  // If intervals are partially overlapping
  let mid = Math.floor((start + end) / 2);
  let left_child
    = query(start, mid, query_start,
      query_end, 2 * idx);
  let right_child
    = query(mid + 1, end, query_start,
      query_end, 2 * idx + 1);
 
  // If length_t of left child is greater
  // than length_t of right child
  if (left_child[0] > right_child[0]) {
    return left_child;
  }
 
  // If length_t of right child is
  // greater than length_t of left child
  if (right_child[0] > left_child[0]) {
    return right_child;
  }
 
  // If length_t of left
  // and right child are equal
  // return there sum
  return [left_child[0],
  left_child[1]
  + right_child[1]];
}
 
// Comparator function to sort an array of pairs
// in increasing order of their 1st element and
// thereafter in decreasing order of the 2nd
function comp(a, b) {
  if (a[0] == b[0]) {
    return a[1] > b[1];
  }
  return a[0] < b[0];
}
 
// Function to find count
// of LIS in the given array
function countLIS(arr, n) {
  // Generating value-index pair array
  let pair_array = new Array(n).fill(0).map(() => []);
  for (let i = 0; i < n; i++) {
    pair_array[i][0] = arr[i];
    pair_array[i][1] = i;
  }
 
  // Sort array of pairs with increasing order
  // of value and decreasing order of index
  pair_array.sort(comp);
 
  // Traverse the array
  // and perform query updates
  for (let i = 0; i < n; i++) {
 
    let update_idx = pair_array[i][1];
 
    // If update index is the 1st index
    if (update_idx == 0) {
      update_tree(0, n - 1, 0, 1, 1, 1);
      continue;
    }
 
    // Query over the interval [0, update_idx -1]
    let temp = query(0, n - 1, 0, update_idx - 1, 1);
 
    // Update the segment tree
    update_tree(0, n - 1, update_idx,
      temp[0] + 1,
      Math.max(1, temp[1]), 1);
  }
 
  // Stores the final answer
  let ans = query(0, n - 1, 0, n - 1, 1);
 
  // Return answer
  return ans[1];
}
 
// Driver Code
 
let arr = [1, 3, 5, 4, 7];
let n = arr.length;
 
document.write(countLIS(arr, n));
 
// This code is contributed by saurabh_jaiswal.
</script>

Python3

# Python program for the above approach
 
import math
 
# Finding the longest increasing Subsequence using
# Segment Tree
class SegmentTree:
     
    # Constructor that initializes the segment tree
    def __init__(self, size):
        # Determine the height of the tree
        height = math.ceil(math.log2(size))
         
        # Determine the maximum size of the tree array
        maxSize = 2 * (2 ** height) - 1
         
        # Create the tree array
        self.tree = [0] * maxSize
 
    # Method that builds the segment tree from an array
    def BuildTree(self, arr, pos, low, high):
         
        # If the segment has only one element, set the
        # corresponding value in the tree
        if low == high:
            self.tree[pos] = arr[low]
            return
 
        # Determine the middle index of the segment
        mid = (low + high) // 2
         
        # Recursively build the left subtree
        self.BuildTree(arr, 2 * pos + 1, low, mid)
         
        # Recursively build the right subtree
        self.BuildTree(arr, 2 * pos + 2, mid + 1, high)
         
        # Set the value of the current node to the maximum
        # value of its children
        self.tree[pos] = max(self.tree[2 * pos + 1], self.tree[2 * pos + 2])
 
    # Method that returns the maximum value in a given
    # range
    def Query(self, pos, low, high, start, end):
         
        # If the given range is fully contained in the
        # current segment, return the corresponding value
        # in the tree
        if start <= low and end >= high:
            return self.tree[pos]
         
        # If the given range does not overlap with the
        # current segment, return the minimum possible
        # value
        if start > high or end < low:
            return float('-inf')
         
        # Determine the middle index of the segment
        mid = (low + high) // 2
         
        # Recursively query the left subtree
        left = self.Query(2 * pos + 1, low, mid, start, end)
         
        # Recursively query the right subtree
        right = self.Query(2 * pos + 2, mid + 1, high, start, end)
         
        # Return the maximum value of the two subtrees
        return max(left, right)
 
class LIS:
    @staticmethod
    # Method that returns the length of the longest
    # increasing subsequence in an array
    def GetLISLength(arr):
        n = len(arr)
         
        # Create a sorted copy of the array
        sortedArr = sorted(arr)
         
         
        # Create a map that maps the elements of the
        # original array to their indices in the sorted
        # array
        indexMap = [0] * n
         
        for i in range(n):
            indexMap[sortedArr.index(arr[i])] = i
     
        # Create a segment tree to store the dynamic
        # programming values
        tree = SegmentTree(n)
         
        # Build the initial tree with all values set to
        # zero
        tree.BuildTree([0] * n, 0, 0, n - 1)
         
        # Create an array to store the dynamic programming
        # values
        dp = [0] * n
 
        for i in range(n):
            prevMax = tree.Query(0, 0, n - 1, 0, indexMap[i] - 1)
            dp[i] = prevMax + 1
            tree.BuildTree(dp, 0, 0, n - 1)
         
        # Searching for the maximum value of longest
        # increasing subsequence
        maxLIS = 0
        for i in range(n):
            maxLIS = max(maxLIS, dp[i])
         
        # Return the maximum value of longest increasing
        # subsequence
        return maxLIS
 
# Driver code
arr = [1, 3, 5, 4, 7]
print(LIS.GetLISLength(arr))
 
 
# This code is contributed by princekumaras

Output

2

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Related Topic: Segment Tree


 


Reffered: https://www.geeksforgeeks.org

Dynamic Programming

Related
Check if end of given Binary string can be reached by choosing jump value in between given range Check if end of given Binary string can be reached by choosing jump value in between given range
Minimize count of 0s in Binary String by changing K-size substring to 1s at most Q times Minimize count of 0s in Binary String by changing K-size substring to 1s at most Q times
Minimum number of days to debug all programs Minimum number of days to debug all programs
Count of index subsets such that maximum of values over these indices in A is at least total sum over B Count of index subsets such that maximum of values over these indices in A is at least total sum over B
Camel and Banana Puzzle | DP Camel and Banana Puzzle | DP

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 10



 

Horje