[알고리즘] 세그먼트 트리 ( Segment Tree ) #3 Update

Update 세그먼트 트리

이번에는 세그먼트 트리에 대한 응용편입니다. 

이미 구성된 세그먼트 트리에서 특정 Node 의 값을 업데이트 하는 방법과 

이 방법에서 반복되는 부분을 제거하여 빠르게 업데이트 하는 방법까지 살펴보겠습니다.

 

Data Sample

다음과 같은 Data를 정의하고 Segment Tree 를 구성한 후, 특정 Node 값을 변경해보겠습니다.

const int MAX = 1000;
const int N = 10;

// Segment Tree : Leaf is update with _data[]
int tree[MAX];

int _data[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 };

 

 

Algorithm

1. 특정 Node 의 값을 업데이트 하기 위해서는 해당 되는 Node 가 Segment Tree 어디에 있는지 먼저 찾아야 합니다.

2. 각 Data Node 는 Segement Tree 의 마지막 Leaf Node 에 위치합니다.

3. 찾아낸 Leaf Node 의 값을 Update 합니다.

4. Update 된 Node 의 부모 Node 들을 값을 Update 해줍니다. 이 과정을 Root 까지 반복해줍니다.

 

예를 들어 기존 Tree 에서 "data[4] = 22" 에 위치한 값을 10 으로 Update 를 한다면, 첫번째로 data[4] 가 Segment Tree 의 어디에 위치하는지 찾아야 합니다.

이유는 변경되는 data 뿐만아니라 구간 연산에 대한 값들도 Update 해야 하기 때문입니다.

data[4] 의 위치 찾기

 

 

두번째로 data[4] 의 값을 10으로 업데이트 합니다.

값을 10으로 업데이트

 

세번째로 data[4] 의 부모의 값(구간합) 을 업데이트 합니다.

부모 노드 (구간합) 업데이트

 

계속해서 Root 까지 업데이트해야 완료 됩니다.

Root 까지 업데이트 완료

 

Implementation

#1 : getLeafNodeIndex

data 가 있는 leaf node 를 찾는 함수

//! tree[p] 의 구간이 (s:start ~ e:end) 이고 그 때 data Index 의 노드번호를 얻을 수 있다.
//! p : 현재 tree 의 위치
//! s : data 시작 위치
//! e : data 마지막 위치
//! return : 현재 위치의 data
int getLeafNodeIndex(int p, int s, int e, int dataidx)
{
    //! 종료 조건 : Start 와 End 가 같다는 것 --> 더이상 확인할 곳이 없다 == Leaf Node
    if (s >= e) {
        //! 종료지점이 data index 와 같다면, 원하는 Node 를 찾은 것이다.
        if (s == dataidx) {
            //! 현재 Segment Tree 의 위치를 Return 해준다.
            return p;
        }
        //! data index 를 찾지 못하고, 끝나는 경우는 -1 을 Return 해주면 호출한 지점에서 구분한다.
        else return -1;
    }
    else {
        //! 종료 지점이 아니면, 하위 Node 를 검색할 수 있다는 의미이다.
        //! 중간 지점을 찾아 Left, Right 각각 검색을 요청할 것(재귀)이다.
        int mid = (s + e) / 2;
        
        //! Left 는 start ~ mid 까지 검색한다.
        int leftIndex = getLeafNodeIndex(p*2, s, mid, dataidx);
        if (leftIndex == -1)
        {
        	//! Left 가 -1 이라면, 못찾은 것이다.
            //! Right 를 검색한다. mid+1 ~ end 까지 검색한다.
            int rightIndex = getLeafNodeIndex(p*2+1, mid+1, e, dataidx);
            return rightIndex;
        }
        else
        	//! left에서 찾았다면 위치를 Return 한다.
        	return leftIndex;
    }
}

 

#2 : updateValue

Leaf Node 를 찾아서 delta 만큰 update 하는 함수

 

※ data 의 크기가 커지면 segment tree 도 함께 커지게 된다.

--> 자주 update 하는 경우에는 getLeafNodeIndex 호출이 부담스러울 수 있다.

//! idx : data index
//! val : value to change
//! idx 의 값을 val 로 update 하는 함수이다.
void updateValue(int idx, int val)
{
    //! data index 를 통해 Node Index(Segment Tree Index) 를 찾는다.
    int treeidx = getLeafNodeIndex(1, 1, n, idx);

	//! update 할 delta 를 구한다.
    int delta = value - _data[idx];

    //! leaf 에서 root 까지 이동하면서 update
    while (treeidx)
    {
    	//! 기존 data 와 차이(delta) 만큼 update
        tree[treeidx] += delta;

		//! 1/2 을 해주면 상위 부모의 index 가 된다.
        treeidx /= 2;
    }
    //! 최종적으로 idx 를 업데이트 해준다.
    _data[idx] = value;
}

 

#3 : Review to improvement

getLeafNodeIndex() 의 경우, 재귀적으로 검색하는 getLeafNodeIndex 이 많은 데이터에서는 시간 낭비의 원인이 될 수 있다.

 

이전 포스팅에서 정의했던 처음 Segment Tree 를 Build 하는 함수를 기억해보자.

처음 tree 를 만들때 데이터를 Tree 에 할당했던 지점에서는 _data 와 tree 간의 관계 정보를 알수 있었다. 데이터를

별도로 저장해놓으면 매번 getLeafNodeIndex( ) 을 호출할 필요가 없을 것이다.

 

이를 위해서 data_to_segtree[ ] 라는 index 만 저장하는 배열 하나를 build_tree 에 추가해주는 방법이다.

//! data index 별 segment tree 의 index 를 저장해놓을 것이다.
int data_to_segtree[MAX];


int build_tree(int p, int s, int e) {
	if (s >= e) { 	//! 재귀 종료 조건 : Leaf Node 도달
    	//! tree 와 _data 간의 관계는 이미 build 할 때 확인할 수 있다.
		tree[p] = _data[s];
        
        //---------------------------------------------------------------
        //! _data 별로 tree 의 index 를 참조할 수 있는 table 을 만들어준다.
        data_to_segtree[s] = p;
        //---------------------------------------------------------------
        
		return tree[p]; //! Leaf Node
	}
    
	int mid = (s + e) / 2;               	      //! 중간위치
	int lval = build_tree(p * 2, s, mid); 	      //! Left
	int rval = build_tree(p * 2 + 1, mid + 1, e); //! Right

	//! Operation
	tree[p] = lval + rval; // Plus
	return tree[p];
}

 

#4 : updateValue2

Leaf Node 를 찾지 않고 바로 update 하는 함수

물론 getLeafNodeIndex ( ) 가 재귀적인 호출을 통해 찾게 되므로(불필요한 검색 발생)

아래와 같이 data_to_segtree[ ] 에서 바로 가져온다면 검색 시간이 필요없다. -> 시간 복잡도는  O(1) 이다.

//! idx : data index
//! val : value to change
//! idx 의 값을 val 로 update 하는 함수이다.
void updateValue2(int idx, int val)
{
    //! Leaf Node 를 찾는 과정을 생략한다.
    //! int treeidx = getLeafNodeIndex(1, 1, n, idx);
    
    //! ---------------------------------------------------------
    //! tree index 를 바로 가져온다. O(1) 이다
    int treeidx = data_to_segtree[idx]
    //! ---------------------------------------------------------

	//! update 할 delta 를 구한다.
    int delta = value - _data[idx];

    //! leaf 에서 root 까지 이동하면서 update
    while (treeidx)
    {
    	//! 기존 data 와 차이(delta) 만큼 update
        tree[treeidx] += delta;

		//! 1/2 을 해주면 상위 부모의 index 가 된다.
        treeidx /= 2;
    }
    //! 최종적으로 idx 를 업데이트 해준다.
    _data[idx] = value;
}

 

※ 마지막까지 detail 하게 고민하면, 알고리즘의 성능을 개선할 수 있을 것입니다.