Обновить один элемент в дереве сегментов

Question

Частью проблемы, которую я решаю, является получение минимума в диапазоне массива (RMQ), поэтому я реализовал дерево сегментов, и пока оно работает нормально. Затем я хочу обновить один элемент в исходном массиве (нет обновлений с более чем одним) и обновить его в дереве сегментов. Что я делаю до сих пор, так это пересекаю дерево сегментов сверху вниз, пока не достигну листьев, но, похоже, в этом есть какая-то ошибка. Вот часть кода обновления, что там не так?

PS n не кратно двум (я не знаю, влияет ли это на решение)

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);
    }
}

PS Есть другие части проблемы, которые могут иметь некоторые ошибки, но кажется, что эта часть, скорее всего, будет иметь ошибку.

Answer 1

Ваша функция обновления не устанавливает и не строит обновленные значения в дереве сегментов правильно.

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. Реализация должна быть примерно такой:

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