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

摘要：

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

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

所属期刊栏目：15

分类号：TP311(计算技术、计算机技术)

在线出版日期：2019-06-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：237-238