セグメントツリー内の1つのアイテムを更新する

Question

私が解決している問題の一部は、配列（RMQ）の範囲内で最小値を取得することを含むため、セグメントツリーを実装しました。次に、元の配列の1つの項目を更新したい（複数の更新がない）と、セグメントツリーで更新したい。私がこれまでに行ったことは、葉に達するまでセグメントツリーを上から下に横断していますが、これにはいくつかのバグがあるようです。ここにコードの更新部分がありますが、何が間違っているようですか？

P.S. nが2の倍数（これは解決策に影響を与える場合、私は知らない）

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.ではありません問題の他の部分にはいくつかのバグがあるかもしれませんが、これはバグを持つ可能性が高い部分です。

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. 
} 

また、ツリーの構築や更新中にたくさんのツリースペースを無駄にしています。余分なスペースの使用を避けるには、現在のノードjの子として2*jと2*j+1を使用します。実装は次のようなものでなければなりません：

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