在某些范围更新后获得整数数组的最终状态的有效算法是什么?

问题描述 投票:2回答:4

我给了一个数组arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}。我必须做一些范围更新。在每次更新中,我将获得三个整数left, right, new_value。这意味着我必须将arr的所有元素从索引left更新为right(从0开始的索引)到new_value。最后,我必须告诉这些更新后数组arr的最终状态是什么。

在这种情况下,假设有2个更新。第一次更新说将0...3更新到13,第二次更新说要将2...6更新为0arr的最终状态是{13, 13, 0, 0, 0, 0, 0, 8, 9, 10}。这是我试过的代码:

int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (size_t i = 1; i <= 2; i++)
    {
        int left, right, new_value;
        cin >> left >> right >> new_value;

        for (size_t j = left; j <= right; j++)
        {
            arr[j] = new_value;
        }
    }
    for (size_t i = 0; i < 10; i++)
    {
        cout << arr[i] << endl;
    }
}

但问题是如果数组的大小是n并且有q查询。然后我的方法的时间复杂性是O(n * q).我的问题是什么将是一个更好的方法?

c++ algorithm
4个回答
2
投票

您需要做的是创建一个中间数据结构,该结构对于进行范围更新而言很便宜。

最简单的数据结构是树。一个实现可以使树的每个节点包含以下字段:

left_index
right_index
left_subtree
right_subtree
is_constant
value

您可以在时间O(n)填充它,使得索引填充,索引相同,子树null,is_constant true和值,然后用is_constant false填充所有上层。

每个更新查询只涉及从上到下遍历。诀窍在于,如果你在树中将is_constant设置得更高,则不需要更新它下面的子树 - 它们都将被“屏蔽”。因此每次更新都是时间O(log(n))

从树复制到您的阵列再次是O(n)操作。

树代码将是适度棘手的,但q查询的总时间是O(n) + O(q * log(n)) + O(n) = O(n + q * log(n))。这是对O(q * n)的重大改进。


以下是树更新的工作原理。

所以我们有一棵树。我们有三个值,left, right, value。然后,更新通过以下Pythonish伪代码递归进行:

def update_tree (self, left, right, value):
    if right < left:
        return # empty interval
    elif right < self.left_index:
        return # No overlap
    elif self.right_index < left:
        return # No overlap
    elif left <= self.left_index and self.right_index <= right:
        # No need to update the subtree - this is our win.
        self.is_constant = True
        self.value = value
    else:
        # We need to only update part of this tree.
        self.is_constant = False
        self.left_subtree.update_tree(left, right, value)
        self.right_subtree.update_tree(left, right, value)

2
投票

有效地执行此操作的最简单方法是维护一个有序集合,该集合仅存储索引0的值以及那些值与前一个索引不同的索引。

由于您使用的是C ++,因此可以将index - > value映射放在std::map<int,int>中。

在每次更新时,您花费O(log n)时间来查找修改地图的位置(使用map.lower_bound),然后您将添加最多2个条目,并且可能删除一些预先存在的条目或您添加的一些条目之前。

预先存在的条目总数<= n,您添加的条目总数<= 2q,因此删除的条目总数为<= n + 2q。

总的复杂性是O(n + q * log n)


1
投票

这似乎也是优先级队列的情况。将查询的每个左右部分与适当的数组单元相关联。

[(13,1), 2, (0,2), (-13,1), 5,
 6, (-0,2), 8, 9, 10]

(If more than one fall on one cell,
 aggregate them.)

现在,当我们从左到右遍历时,我们对一件事情感兴趣:我们当前在哪个更新间隔(如果有的话)在最后的查询中提供?后者“排名”是查询部分的优先级。

我们从(13,1)开始,我们将其置于优先级队列中并保持输出13直到达到(0,2)。我们将(0,2)添加到优先级队列,这需要更高的优先级。我们继续输出0.我们到达(-13,1),它告诉我们从优先级队列中删除(13,1),并继续putput 0直到(-0,2)调用删除(0,2) )。我们以8,9,10结束。


0
投票

将间隔代数应用于您的查询。新查询优先于旧查询。在您发布的情况下,您可以从一张干净的纸张开始第一个查询添加了事务

0   3    13

第二个更新此表

0   1    13     // note the range change -- intervals may not overlap
2   6     0

大多数语言都有间隔模块,可以为您提供支持。对您的表进行排序,使得对于新查询的每个端点,搜索不会比O(log q)差 - 并且直接索引方法会将此删除为O(n)。

在您不在查询之前不要进行任何更新。间隔过程为O(q),更新为O(n),因此您的总体复杂度为O(q + n)。

© www.soinside.com 2019 - 2024. All rights reserved.