最长递增子序列的长度（LIS）使用线段树

段树是一种多功能的数据结构，旨在以对数时间复杂度回答范围查询和执行数组更新操作，其中每个节点存储与数组中特定范围的元素相关的信息。

在最长递增子序列（LIS）问题的背景下，需要确定给定序列中元素按递增顺序排序的最长子序列的长度，可以利用线段树来高效计算数组中最长递增子序列的长度。

这种方法与传统方法相比显著降低了时间复杂度，并在基因组学、自然语言处理和模式识别等领域有许多应用。本文探讨了段树的基本原理，并展示了它们在解决最长递增子序列问题中的潜力。

语法

Segment Tree build function −

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

Segment Tree query function −

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

段树更新函数 −

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

算法

使用线段树找到最长递增子序列（LIS）的长度的算法如下 -

• 初始化表示输入序列的数组。

使用与输入序列相同大小的段树进行初始化 使用build函数构建线段树

• 处理输入序列的每个元素。

• 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.

• 对输入序列中的所有元素重复执行步骤4-6。

• 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;
}

输出

Length of Longest Increasing Subsequence: 3

使用带有延迟传播的段树的方法

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

Example 2

下面的代码演示了如何使用带有延迟传播的段树在C++中找到最长递增子序列（LIS）的长度。这段代码与方法1的代码相似，两种方法之间的主要区别在于段树的内部实现。懒惰传播技术在这段代码中没有明确显示，因为它优化了特定用例的更新函数，而这些用例在LIS问题中不存在。然而，代码的基本结构保持不变，并且构建、查询和更新函数的使用方式与方法1中的类似。

#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;
}

输出

Length of Longest Increasing Subsequence: 3

Conclusion

在本文中，我们通过C++中的线段树技术来说明确定最长递增子序列（LIS）的范围的方法。我们阐述了两种方法：一种是直接执行线段树，另一种是利用延迟传播的改进方法。这两种技术在解决LIS问题上都很有效，而优化方法中的延迟传播进一步降低了时间复杂度。