arrays - 在数组中搜索特定范围内的整数

Question

有人可以给我解决以下问题的想法吗？

给定一个数组 ar[]长度n ，以及一些查询，每个查询的形式都是 a, b, c ，找到索引最小的数i这样索引位于 [c, n] 范围内这样 a < ar[i] < b .有(n - 1)总共c来自 1至 n - 1 .每个查询的预期复杂度应约为 O(log n) ，以及最多 复杂度的预计算 O(n log n) 是合适的。凭直觉，我想到了线段树，但我想不出构建它的方法，也想不出每个节点要保留什么。

Answer 1

好的，我认为我应该实现我与 user12861 讨论的 O(nlogn)/O(logn) 解决方案。

代码通过构建 n 树来工作，每个 c 一棵树。每棵树与较小的树共享其大部分内容，最多有 logn 个新节点。这样，预处理的总内存和时间成本限制为 O(nlogn)。

实际的树与区间树非常相似。节点存储它们跨越的最小值和最大值，以及它们包含的最小索引。然而，我的实现不是自平衡的，但这可以使用您最喜欢的启发式方法添加。

import sys

class Node:
    pass
class Interval(Node):
    def __init__(self,left,val,i,right):
        self.i = i; self.val = val
        self.left = left; self.right = right
        self.mini = min(left.mini, i, right.mini)
        self.min = min(left.min, val, right.min)
        self.max = max(left.max, val, right.max)
    def add(self,val,i):
        # We do naive inserting here. In a real worst case logn solution,
        # self-balancing would take place here.
        if (val,i) < (self.val,self.i): return Interval(self.left.add(val,i), self.val, self.i, self.right)
        if (self.val,self.i) < (val,i): return Interval(self.left, self.val, self.i, self.right.add(val,i))
        return self
    def query(self,a,b):
        # If the entire interval is covered, return mini, this is what keeps us
        # at max 2 opened nodes per level in the tree.
        if a <= self.min and self.max <= b: return self.mini
        # Otherwise compose an answer from the subtrees.
        res = sys.maxint
        if a <= self.val <= b: res = min(res, self.i)
        if self.left.min <= b and self.left.max >= a: res = min(res, self.left.query(a,b))
        if self.right.min <= b and self.right.max >= a: res = min(res, self.right.query(a,b))
        return res
class Tip(Node):
    def __init__(self):
        # This is a typical null-pattern idiom. The self.values are set to
        # the min/max identities to ensure to interference with the upwards
        # value propagation.
        self.mini = sys.maxint
        self.min = sys.maxint
        self.max = -sys.maxint
    def add(self,val,i):
        return Interval(Tip(), val, i, Tip())
    def query(self,a,b):
        return sys.maxint

# The input data array
data = [0, 3, 1, 2, 0, 4, 9, 6, 1, 7]
N = len(data)

# Build the array of trees. O(nlogn)
ar = [None]*N + [Tip()]
for i in range(N-1, -1, -1):
    ar[i] = ar[i+1].add(data[i],i)

# The query function. O(logn)
def query(a,b,c):
    return ar[c].query(a,b)

# Test
print query(2, 7, 4) # = 5