Length of longest increasing subsequence (LIS) using line segment trees

A segment tree is a versatile data structure designed to answer range queries and perform array update operations in logarithmic time complexity, where each node is stored with a specific range in the array Information related to the element.

In the context of the longest increasing subsequence (LIS) problem, it is necessary to determine the length of the longest subsequence in which the elements in a given sequence are sorted in increasing order. Line segment trees can be used to efficiently calculate the length of the longest increasing subsequence in the array. length.

This method significantly reduces the time complexity compared with traditional methods and has many applications in fields such as genomics, natural language processing, and pattern recognition. This article explores the fundamentals of segment trees and demonstrates their potential in solving the longest increasing subsequence problem.

grammar

Segment Tree build function −

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index)
</int>

Segment Tree query function −

int query(const vector<int> &tree, int start, int end, int l, int r, int index)

Segment tree update function −

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index)

algorithm

The algorithm for finding the length of the longest increasing subsequence (LIS) using a line segment tree is as follows -

• Initialize the array representing the input sequence.

Initialize with a segment tree of the same size as the input sequence Use the build function to build a line segment tree

• Process each element of the input sequence.

• For each element, query the Segment Tree to find the maximum length of LIS ending at the current element.

• Update the Segment Tree using the update function.

• Repeat steps 4-6 for all elements in the input sequence.

• The final answer is the maximum value stored in the Segment Tree.

Approach 1: Using simple Segment Tree

In this approach, we implement a simple Segment Tree without any optimization techniques such as lazy propagation.

Example-1

The program below demonstrates how to find the Length of Longest Increasing Subsequences (LIS) using a simple Segment Tree in C . The build, query, and update functions are used to construct the Segment Tree, retrieve the maximum length of LIS ending at a specific element, and update the Segment Tree with new LIS lengths, respectively. The lengthOfLIS function iterates through each element in the input sequence and computes the LIS length using the Segment Tree.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
   if (start == end) {
      tree[index] = arr[start];
   } else {
      int mid = start + (end - start) / 2;
      build(tree, arr, start, mid, 2 * index + 1);
      build(tree, arr, mid + 1, end, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
   if (l <= start && end <= r) {
      return tree[index];
   }
   if (end < l || r < start) {
      return 0;
   }
   int mid = start + (end - start) / 2;
   return max(query(tree, start, mid, l, r, 2 * index + 1),
      query(tree, mid + 1, end, l, r, 2 * index + 2));
}

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
   if (pos < start || end < pos) {
      return;
   }
   if (start == end) {
      tree[index] = value;
   } else {
      int mid = start + (end - start) / 2;
      update(tree, arr, start, mid, pos, value, 2 * index + 1);
      update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int lengthOfLIS(const vector<int> &nums) {
   int n = nums.size();
   vector<int> arr(n, 0), tree(4 * n, 0);

   build(tree, arr, 0, n - 1, 0);

   for (int num : nums) {
      int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
      update(tree, arr, 0, n - 1, num, lis_len, 0);
   }

   return query(tree, 0, n - 1, 0, n - 1, 0);
}

int main() {
   vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
   cout << "Length of Longest Increasing Subsequence: " <<lengthOfLIS(nums) << endl;
   return 0;
}

Output

Length of Longest Increasing Subsequence: 3

Method using segment tree with delayed propagation

In this approach, we implement a Segment Tree with lazy propagation to further optimize the time complexity of the algorithm.

Example 2

The following code demonstrates how to find the length of the longest increasing subsequence (LIS) in C using segment trees with delayed propagation. This code is similar to the code for method 1, the main difference between the two methods is the internal implementation of the segment tree. The lazy propagation technique is not explicitly shown in this code because it optimizes the update function for specific use cases that do not exist in the LIS problem. However, the basic structure of the code remains the same, and the build, query, and update functions are used in a similar way to method 1.

<int>#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
    if (start == end) {
        tree[index] = arr[start];
    } else {
        int mid = start + (end - start) / 2;
        build(tree, arr, start, mid, 2 * index + 1);
        build(tree, arr, mid + 1, end, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
    if (l <= start && end <= r) {
        return tree[index];
    }
    if (end < l || r < start) {
        return 0;
    }
    int mid = start + (end - start) / 2;
    return max(query(tree, start, mid, l, r, 2 * index + 1),
               query(tree, mid + 1, end, l, r, 2 * index + 2));
}
void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
    if (pos < start || end < pos) {
        return;
    }
    if (start == end) {
        tree[index] = value;
    } else {
        int mid = start + (end - start) / 2;
        update(tree, arr, start, mid, pos, value, 2 * index + 1);
        update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int lengthOfLIS(const vector<int> &nums) {
    int n = nums.size();
    vector<int> arr(n, 0), tree(4 * n, 0);
    build(tree, arr, 0, n - 1, 0);
    for (int num : nums) {
        int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
        update(tree, arr, 0, n - 1, num, lis_len, 0);
    }
    return query(tree, 0, n - 1, 0, n - 1, 0);
}
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of Longest Increasing Subsequence: " << lengthOfLIS(nums)
         << endl;
    return 0;
}
</int>

Output

Length of Longest Increasing Subsequence: 3

Conclusion

In this article, we illustrate the method of determining the range of the longest increasing subsequence (LIS) through the line segment tree technology in C. We illustrate two approaches: one that directly performs segment trees, and the other that exploits an improved method of delayed propagation. Both techniques are effective in solving LIS problems, and delay propagation in the optimization method further reduces the time complexity.

The above is the detailed content of Length of longest increasing subsequence (LIS) using line segment trees. For more information, please follow other related articles on the PHP Chinese website!