查找比数组给定数字的比较大的数字

Question

有数字的UNSORTED序列：a1,a2,...,an

而且，我们有一个数字，我所以我们有人工智能

我们希望发现号，j，它j<i和aj>ai 像这样：

3,4,9,1,8,10,2,2,6,1 
if i=8 then j=6 
if i=7, j=6 again 
if i=10 then j=9 
if i=1 then j=NIL (Not In List) 

Answer 1

使用Segment tree可以在O（n）预处理和O（log n）每个查询中执行此操作。

在每个查询的O（log^2 n）中执行它非常简单。首先，构建支持在O（log n）上的段上获得最大值的分段树。其次，为每个查询做一个二进制搜索。

我表示max(a_i, ..., a_j) as max(i, j)。说查询索引是i。如果max(i+1, n) <= a_i那么显然没有这样的元素。否则，你必须找到一个最小的j，这样max(i+1, j) > a_i，这是通过在j上进行二分搜索完成的。

为了进一步改进，您已经深入了解了分段树结构。我会给你基本的想法。假设您必须在数组中找到大于x的第一个元素。最初，您位于分段树的根部。如果左侧子树的最大值为> x，则您转到左侧子树，否则转到右侧。可以很容易地看出，您完成的叶子对应于数组的最左边的元素，即> x。