基于线段树维护的上升序列算法的研究与实现

荆慧

摘要：经典的最长上升子序列算法复杂度较高，且不适用于序列元素值更改的情况。本文解决的问题是经典问题的变形，在原有问题基础上对序列值进行m次修改，每次修改后求解在原点可以看到几个柱子。在经典求解最长上升子序列长度算法的基础之上，利用线段树对区间值进行修改、维护和查询，求解上述问题，将时间复杂度降到了[Omlog2n]。

关键词：最长上升子序列；上升序列；线段树；区间修改

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）10-0237-02

开放科学（资源服务）标识码（OSID）：

最长上升子序列问题在计算机算法领域是非常经典的问题，经典算法是使用动态规划算法进行求解。动态规划算法是求解决策过程的有效最优数学方法之一，为具有最优解结构性质的实际问题提供了行之有效的解决方法[1-2]。动态规划算法先把原问题分解为易于解决的子问题，再将子问题合并为原问题。利用最优解性质建立的子问题最优值的递推关系可以自底向上递推地从子问题的最优解逐步构造出整个问题的最优解，大量降低时间和空间复杂度。[3]最长上升子序列算法不适用于带修改序列元素的问题，且时间复杂度较高。本文在经典算法的基础上，对于经典问题的变形问题，提出了一种更加灵活高效的算法。

1 基于线段树查询修改的上升序列优化算法

1.1 问题描述

经典问题描述为：设A=[a1，a2，a3，…，an]是长度为n的序列，该序列存在子序列B=[ai1，ai2，ai3，…，ail]，其中满足条件[ai1

问题描述为，已知序列[A=a1，a2，a3，…，an]，A序列初始元素为0，A序列元素代表柱子的高度。可对序列进行m次修改，格式为（x，y），意为将第x个柱子高度修改为y，求解每次修改完成后的在原点可见的柱子个数。

1.2 问题思路

用线段树维护区间的序列元素最大值和该区间内最长上升子序列的长度。当序列元素被修改，直接用普通的线段树更新即可；求解上升序列，也可以利用线段树查询更新。可以看出，当一个序列元素值被修改，它只会对后面的部分产生影响。利用这个特性，进行线段树更新修改。

1.3 问题求解

设Max[rt]为：仅考虑rt所代表的区间，序列元素的最大值。

设cnt[rt]为：仅考虑rt所代表的区间，有多少满足条件的数 ，即满足上升序列的长度。首先，cnt[rt]一定包含它的左子树求值结果cnt[rt*2]； 其次，属于cnt[rt*2]中的序列元素值可能有比cnt[rt*2+1]中的序列元素值大，那么cnt[rt*2+1]的结果就会被cnt[rt*2]的结果影响，线段树区间合并时要注意这个问题，重点在于求解被影响后的cnt[rt*2+1]的结果值。

设 rt*2 代表的区间中最大高度值为maxn1，将 rt*2+1 所代表的区间分左右两个子树，左子树区间中最大高度值为maxn2，进行讨论：

1） 若maxn1>=maxn2，递归判断右子树还多少个大于maxn1的值。

2） 若maxn1

输入：序列长度n和修改序列次数m，之后给出n行，每行的形式为（x，y），意为将第x个元素修改为y。

输出：每次修改后，输出上升序列的长度。

1.int x，y，n，m //定义变量

3.scanf（"%d%d"，&n，&m）

4.for i=1 to m do

5.scanf（"%d%d"，&x，&y）

6.change（y，x，1，1，n） //线段树更新

7.printf（"%d＼n"，cnt[1]）//整个序列的最长上升子序列长度

从时间复杂度来看，i每次从1循环到m，由于每次循环体内时间复杂度为O（[log2n]），由此可見改进后的算法时间复杂度为[Omlog2n]。

线段树统计区间上升序列长度函数num：

1.int mid=（left+right）/2

2.if（left==right） then

3.返回maxn

4.if（maxn>=Max[rt*2]） then

5.递归返回num（maxn，rt*2+1，mid+1，right）

6.递归返回cnt[rt]-cnt[rt*2]+num（maxn，rt*2，left，mid）

线段树更新函数change：

1.int mid=（left+right）/2

2.if（left==right） then

3.cnt[rt]=1

4.Max[rt]=k

5.return返回

6.if（x<=mid） then

7.change（k，x，rt*2，left，mid）

8.if（x>mid） then

9.change（k，x，rt*2+1，mid+1，right）

10.Max[rt]：=max（Max[rt*2]，Max[rt*2+1]）

11.cnt[rt]：=cnt[rt*2]+num（Max[rt*2]，rt*2+1，mid+1，right）

2 兩种算法时间复杂度和空间复杂度的比较

使用经典算法解决该问题的时间复杂度为[Omn2]，空间复杂度为[On]；

本文算法时间复杂度为[Omlog2n]，空间复杂度为[On]。本文算法将动态规划问题最优子解的性质和线段树维护更新的性质相结合，在空间复杂度差别不大的情况下，将算法复杂度优化到了平方数量级以下。

对序列元素值进行m次修改，每次修改元素区间维护的时间复杂度O（[log2n]）。

3 结束语

文中探讨了基于线段树查询修改的上升序列的变形优化问题，通过经典算法和本文算法的比较，最终将时间复杂度控制在平方数量级的范围内，有效地降低了该类问题的时间复杂度，为后续的应用推广奠定了基础。

参考文献：

[1] Alsuwaiyel MH.Algorithms design techniques and analysis[M].Beijing：Publishing House of Electronics Industry.2003.

[2] Cooper R.Dynamic programming： An overview[EB/OL].2001.http： //econ.bu.edu /faculty /cooper/Dynprog /introlect.pdf.

[3] 郭冬梅.基于状态压缩的最长公共上升子序列快速算法[J].计算机技术与发展，2014，24（05）：40-43.

【通联编辑：梁书】

附录：①程序C++源代码

#include

using namespace std；

const int N=400010；

int cnt[N]；

double Max[N]；

int num（double maxn，int rt，int left，int right）

{

int mid=（left+right）/2；

if（left==right）

return maxn

if（maxn>=Max[rt*2]）

return num（maxn，rt*2+1，mid+1，right）；

return cnt[rt]-cnt[rt*2]+num（maxn，rt*2，left，mid）；

}

void change（double k，int x，int rt，int left，int right）

{

int mid=（left+right）/2；

if（left==right）

{

cnt[rt]=1；

Max[rt]=k；

return；

}

if（x<=mid）

change（k，x，rt*2，left，mid）；

else

change（k，x，rt*2+1，mid+1，right）；

Max[rt]=max（Max[rt*2]，Max[rt*2+1]）；

cnt[rt]=cnt[rt*2]+num（Max[rt*2]，rt*2+1，mid+1，right）；

}

int main（）

{

double x，y；

int n，m；

scanf（"%d%d"，&n，&m）；

for（int i=1；i<=m；i++）

{

scanf（"%lf%lf"，&x，&y）；

change（y/x，（int）x，1，1，n）；

printf（"%d＼n"，cnt[1]）；

}

return 0；

}