세그먼트 트리 : 구간별로 비교할 경우 (feat. BOJ : 히스토그램에서 가장 큰 직사각형 )

세그먼트 트리의 원리 : 연속된 구간의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 트리

원리는 쉽다. 입새노드를 좌에서 우로 순서대로 배치한다. 트리의 크기는 아무리커도 배열크기의 원소들이

입새노드가 될 수 있으면 된다. 아래 식을 확인해보면 이해할 수 있다.

부모노드는 자식노드의 합산으로 결정되고 부모값이 의미하는 바는 자식노드들의 합산이 된다.

부모노드들은 결국 해당구간의 합산을 기억하고 있으며 필요한 범위를 지정하면 접근하도록 구현하면 완성된다.

편의를 위해 루트노드의 인덱스는 1로 왼쪽 자식은 *2 , 오른쪽 자식은 *2+1 한값을 기억하도록 한다.

 

코드 : 자바

int h= (int) Math.ceil(Math.log(N)/ Math.log(2));
h = (int)Math.pow(2, h+1);
tree = new int[h];
init_tree(0,N-1,1); //트리 생성
System.out.println(search(0,N-1,1,0,5)); //파라미터 앞에 3개는 고정 0이상 5이하 인덱스 서치

////////////////////////////////////////////////////////////////////////////////
public static int init_tree(int start,int end,int idx) {
		if(start==end) { //입새노드를 찾았다.
			tree[idx] = table[start];
			return tree[idx];
		}
		int mid = (start+end)/2; //mid를 중심으로 좌우로 나눈다.
		tree[idx] = init_tree(start,mid,idx*2)+init_tree(mid+1,end,idx*2+1);
		return tree[idx];
	}

	public static int search(int start,int end, int idx, int left, int right) {
		if(left>end || right< start) { //완전 무관한 가지이라면 무시한다.
			return 0;
		}
		else if( left<=start && right >=end) { // 완전히 속하면 수행
			return tree[idx];
		}
        //걸쳐있다는 것이므로 왼쪽과 오른쪽 구분해서 처리
		int mid = (start+end)/2;
		return search(start,mid,idx*2,left,right)+search(mid+1,end,idx*2+1,left,right);
			
	}

해당코드는 부분합을 기억하는 트리를 만든 것이다. 매커니즘을 이해하면 범위내의 최솟값 등을 찾을 수 있도록 변형할 수 있다. 

 

응용 문제 백준 6549 : 히스토그램에서 가장 큰 직사각형

GitHub - lyeong-gwa/algorithm_study: 알고리즘 공부!