세그먼트 트리에서 한 항목 업데이트

Question

문제의 일부분은 배열 (RMQ)의 범위에서 최소값을 얻는 것과 관련되어 있으므로 세그먼트 트리를 구현했으며 지금까지는 문제가 없습니다. 그런 다음 원래 배열에서 하나의 항목을 업데이트하고 (둘 이상의 항목이있는 업데이트가 없음) 세그먼트 트리에서 업데이트하려고합니다. 내가 지금까지 할 일은 나뭇잎에 도착할 때까지 세그먼트 트리를 위에서 아래로 가로지 릅니다. 그러나 이것에 약간의 버그가있는 것 같습니다. 다음은 코드의 업데이트 부분입니다. 거기에 잘못된 것 같습니다.

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

또한 트리를 작성하고 업데이트하는 동안 많은 나무 공간을 낭비하고 있습니다. 여분의 공간 사용을 피하려면 2*j 및 2*j+1을 현재 노드 j의 자식으로 사용하십시오. 구현은 다음과 같아야합니다.

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