algorithm - 在给定的数组范围内找到最接近 P 的数字

Question

给你一个包含 N 个整数的数组 A。您需要对数组进行 Q 查询。查询有两种类型。

1 U P:你需要将A_u的值更新为P。

2 L R P:你需要找到 A_k 使得 A_k - P 最小并且 A_k> P 和 L<= k<=R

输入格式:

输入的第一行包含一个整数 N。下一行包含 N 个以空格分隔的整数，数组 A 的元素。

下一行输入包含一个中间 Q。

Q 行之后，每行包含一个查询，如声明中所述。

输出格式:

对于类型 2 的查询，您需要打印 A_k 的值。如果没有这样的 K 打印 -1。在新行中打印每个查询的答案。

Example Input:                               Example Output:
5                                            2
3 2 1 1 5                                    -1
3
2 1 5 1
1 4 4
2 1 4 5

解释:对于[1,5]和P=1范围内的第一个查询，所需的A_k为2。

我正在考虑针对查询类型 2 的 O(log(N)) 的线段树解决方案。但不知道该怎么做。

Answer 1

让我们考虑上面的示例并在其之上构建我们的算法。

所以我们的输入看起来像这样:-

Example Input:                               Example Output:
5                                            2
3 2 1 1 5                                    -1
3
2 1 5 1
1 4 4
2 1 4 5

现在我正在构建一个线段树，它在 (min, max) 的每个节点上保留两个值，min 对应于该范围内的最小值，并且 max 值对应于该范围内的最大值。

现在，在运行上述示例的构建方法后，我们的线段树将如下所示:-

                [0:4] (1,5)
              /             \
             /               \
        [0:2] (1,3)           [3:4] (1,5)
       /         \            /         \
      /           \          /           \
   [0:1] (2,3)   [2:2](1,1) [3:3](1,1)  [4:4](5,5)
  /       \
 /         \
[0:0](3,3)  [1:1](2,2)

所以你可以在上面的线段树中看到，在每个级别，每个节点如何由该区间内的一对 (min, max) 组成。

现在让我们用伪代码的形式看一下我们的更新查询。这非常简单。

void update(int node, int start, int end, int idx, int val)
{
if(start == end)
{
    // Leaf node
    A[idx] = val;
    tree[node] = val;
}
else
{
    int mid = (start + end) / 2;
    if(start <= idx and idx <= mid)
    {
        // If idx is in the left child, recurse on the left child
        update(2*node, start, mid, idx, val);
    }
    else
    {
        // if idx is in the right child, recurse on the right child
        update(2*node+1, mid+1, end, idx, val);
    }
    // Internal node will have the min and max of both of its children
    tree[node] = pair(min(tree[2*node].min, tree[2*node+1].min), max(tree[2*node].max, tree[2*node+1].max);
}

}

更新非常清楚，我们只需要到达叶值并更新该索引处的值，然后递归回到顶部，我们将继续使用最小值和最大值更新我们的其他节点。

更新查询的时间复杂度是O(logn)。

现在让我们来看看问题的主要组成部分，即问题的查询部分。

所以我们的代码查询部分看起来像这样:-

// P here is the value for which our Ak > P and Ak - P shoudl be minimum
// l and r is our range provided in the input for each query
int query(int node, int start, int end, int l, int r, int P)
{
    // If the maximum element at this particular node of the tree is less than P,
    // then there is no point in going down as we need to find the element which is greater than P.
    if(tree[node].max < P) 
    {
      return -1;
    }
    if(r < start or end < l)
    {
        // range represented by a node is completely outside the given range
        return -1;
    }
    if(l<=start and end <= r and start==end) {
      return tree[node] - P;
    }
    // range represented by a node is partially inside and partially outside the given range
    int mid = (start + end) / 2;
    int p1 = query(2*node, start, mid, l, r);
    int p2 = query(2*node+1, mid+1, end, l, r);
    return min(p1 + p2);
}

我在伪代码中添加了尽可能多的注释，如果我有任何错误，请看一下并告诉我。

希望这对您有所帮助!