问查找比数组中给定的数字更大的数字

EN

可以使用段树在O(n)预处理和每个查询中执行O(log )。

在每个查询中使用O(log^2，n)进行这一操作非常简单。首先，构建一个分段树，它支持在O(log )上的一个段上获得最大值。第二，对每个查询执行二进制搜索。

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

为了进一步改进，您必须深入到段树结构中。我会给你一个基本的想法。假设您必须在数组中找到大于x的第一个元素。最初，您位于段树的根上。如果左子树的最大值是> x，那么您将转到左边的子树，其他的则转到右边。可以很容易地显示，您完成的叶对应于数组的最左边元素，即> x。