2-3树的最长增长子序列

Question

在为我的数据结构做最后的准备时，我遇到了以下问题：

长度为n的给定整数数组。

提出支持下列操作的数据结构：

Init( A ) -给定数组A的结构初始化。最坏的情况复杂性: O(nlogn)。LengthOfLongest() -返回A(元素)最长单调递增s的长度。最坏情况复杂性: O(1)。

我知道这是一个众所周知的问题，我知道相关的wiki文章。然而，解决方案对我来说是不直观的。

我得到了一个提示，这个问题也可以通过2-3等级树来解决。

有人能解释一下使用2-3树的解决方案吗？

例如:对于数组A= {10,9, 11，8, 12，7,13}，最长的子数组是{10，11，12，13}，它的长度是4。

Answer 1

这是一个研究得很好的问题，称为最长增长子序列，可以在O(n log n)时间内解决。请参阅subsequence