在给定的数组范围内找到最接近 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 个 space 分隔的整数，数组 A 的元素。

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

Q 行，每行包含语句中所述的查询。

输出格式：

对于类型2的query，需要打印A_k的值。如果没有这样的K print -1.Print new中每个query的answer线。

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.But 的 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);
}

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

希望对您有所帮助！

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

Find closest number to P in a given range of array

algorithm

data-structures

segment-tree