c++ - 在一些范围更新后获得整数数组最终状态的有效算法是什么？

Question

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

在这种情况下，假设有 2 个更新。第一次更新说更新索引0...3到13第二次更新说更新2...6到0。的最终状态arr是{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

Answer 1

你需要做的是创建一个中间数据结构，它可以很便宜地进行范围更新。

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

left_index
right_index
left_subtree
right_subtree
is_constant
value

您可以O(n)通过使用相同的索引填充叶子、子树 null、 true 和值来及时填充它，然后用falseis_constant填充所有上层。is_constant

每个更新查询只涉及自上而下的遍历。诀窍是，如果您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)