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

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

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

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

语法

Segment Tree build function −

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

登录后复制

Segment Tree query function −

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

登录后复制

段树更新函数 −

void update(vector &tree, const vector &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
#include
#include

using namespace std;

void build(vector &tree, const vector &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 &tree, int start, int end, int l, int r, int index) {
if (l