자료구조

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

Indexed Tree

 인덱스 트리(Indexed Tree)는 N개의 데이터를 사용하여 2N크기의 이진 트리를 생성하고 각 범위를 대표하는 값(최대, 최소, 누적합 등)을 이진트리 형태로 저장하여, 이후에 한 구간 [l, r]에 대한 대표값을 O(log2(N))만에 구할 수 있게 해주는 형태입니다.

 인덱스 트리가 중요한 이유는 데이터가 갱신되어도 이 갱신된 결과를 반영하는 것이 O(log2(N))의 시간복잡도는 가지는 점이며, 이는 데이터를 단순히 배열으로 저장했을때와 가장 큰 차이가 됩니다.

#define vi vector<int>
#define mid (lm+rm)/2
#define LQR l, r, lm, mid, pos*2
#define RQR l, r, mid+1, rm, pos*2+1

struct IT{
        int lv, w;
    	vi minv, maxv;
    	//0-based
    	void update( int pos,int val ){
            	pos += w;
            	minv[pos] = maxv[pos] = val;
            	while(pos /= 2){
                    	maxv[pos] = max(maxv[pos*2], maxv[pos*2+1]);
                    	minv[pos] = min(minv[pos*2], minv[pos*2+1]);
            	}
    	}
    	IT(int N ){
            	for(lv=0, w=1;  w<N;  w*=2,lv++);
            	minv = maxv = vi(w*2+1);
    	}
    	//사용법 : maxq(l,r)  단, [l,r ]은 0-based
    	int maxq(int l, int r, int lm=0,int rm=0, int pos = 1){
            	if(pos == 1) rm = w-1;
            	if( r < lm || rm < l )  return -1e9;
            	if( l <= lm && rm <= r )    	return maxv[pos];
            	return max( maxq(LQR), maxq(RQR));
    	}
    	int minq(int l, int r, int lm=0,int rm=0, int pos = 1){
            	if(pos == 1) rm = w-1;
            	if( r < lm || rm < l )  return 1e9;
            	if( l <= lm && rm <= r )    	return minv[pos];
            	return min( minq(LQR), minq(RQR));
    	}
};
 

 

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기