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

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

П.С. 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);
    }
}


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


c# algorithm rmq segment-tree
person Ayman El Temsahi    schedule 27.09.2016    source источник
comment
Следующее выглядит подозрительно: tree[j] = Math.Min(tree[j], k); Старое значение дерева[j] теряется. Разве вы не хотите поменять местами дерево[j] и k?   -  person jdweng    schedule 28.09.2016
comment
что вы имеете в виду поменять местами дерево [j] и k? массив дерева - это массив дерева сегментов, я хочу, чтобы дерево [j] имело мин поддерева под ним после изменения значения в основном массиве   -  person Ayman El Temsahi    schedule 28.09.2016
comment
Я не проверял алгоритм. Код, который вы используете, будет работать только в том случае, если дерево [j] пусто. Если дерево[j] уже содержит значение, вы переопределяете существующее значение без сохранения результатов.   -  person jdweng    schedule 28.09.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

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);
person Obaida.Opu    schedule 28.09.2016
comment
Obaida.Opu Привет. Я использовал ваш подход в rmq, но получаю неправильные ответы. Пожалуйста помоги. Это ссылка на мой вопрос в stackoverflow. Я был бы очень признателен. Спасибо - person Brij Raj Kishore; 09.09.2017