更新细分树中的一项 [英] Update one item in segment tree

问题描述

我要解决的问题的一部分涉及获得数组范围（RMQ）的最小值，因此我实现了一个细分树，到目前为止效果很好。然后，我想更新原始数组中的一项（没有多于一项的更新）并在细分树中进行更新。到目前为止，我所做的是从上到下遍历段树，直到到达叶子为止，但这似乎有一些错误。这是代码的更新部分，那里似乎有什么问题？



P.S. n不是2的倍数（我不知道这是否会影响解决方案）

A part of a problem I'm solving involves getting the minimum in a range of an array (RMQ), so I implemented a segment tree and it works fine so far. Then I want to update one item in the original array (There are no updates with more than one) and update it in the segment tree. What I do so far is traverse the segment tree from top to bottom till I reach the leaves, but there seems to be some bug in this. Here is the update part of the code, what seems to be wrong there ?

P.S. n is not a multiple of two ( I don't know if this affects the solution )

public void update(int i, int k) {
    update(i, k, 0, 0, n - 1);
}
/// <summary>
/// update one item in the segment tree
/// </summary>
/// <param name="i">The index of the element to be updated in the original array</param>
/// <param name="k">The new value</param>
/// <param name="j">The current index in the segment tree</param>
/// <param name="from">range start index (inclusive)</param>
/// <param name="to">range end index (inclusive)</param>
private void update(int i, int k, int j, int from, int to) {
    tree[j] = Math.Min(tree[j], k);
    if (from == to) return;

    int mid = from + (to - from) / 2;

    if (from <= i && mid >= i) {
        update(i, k, 2 * j + 1, from, mid);
    } else {
        update(i, k, 2 * j + 2, mid + 1, to);
    }
}

问题的其他部分可能会有一些错误，但是似乎这是最有可能出现此错误的部分。

P.S. There are other parts of the problem that may have some bugs, but it seems that this is the part most likely to have the bug.

推荐答案

您的更新功能未正确设置并建立细分树中的更新值。

Your update function doesn't set and build up the updated values in the segment tree correctly.

private void update(int i, int k, int j, int from, int to) {

    if (from == to) {
        tree[j] = k; //set the new leaf value.
        return;
    }

    int mid = (from+to)/2;

    if (from <= i && mid >= i) {
        update(i, k, 2 * j + 1, from, mid);
    } else {
        update(i, k, 2 * j + 2, mid + 1, to);
    }
    tree[j] = Math.Min(tree[2*j+1], tree[2*j+2]); //keep correcting minimums for every parents with the current minimum.
}

在构建和更新树时，您也在浪费大量树空间。为避免额外的空间使用，请使用 2 * j 和 2 * j + 1 作为当前节点j的子节点。实现应该是这样的：

Also you are wasting a lot of tree space while building and updating the tree. To avoid extra space usage, use 2*j and 2*j+1 as the child of current node j. Implementation should be something like this:

update(i, k, 2*j, from, mid);
update(i, k, 2*j+1, mid+1, to);

这篇关于更新细分树中的一项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！