알고리즘 문제 해결 전략 2 6장 트리 (6)

24 구간 트리

24.1 구간 트리: 구간에 대한 질문 대답하기

segment tree는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 함. 해당 배열을 전처리해 구간 트리를 생성하면 같은 연산을 빠르게 구현할 수 있음. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것임. 

 

구간 트리의 표현

꽉 찬 이진 트리는 이진 검색 트리처럼 포인터로 연결된 객체로 표현하기보다 배열로 표현하는 것이 메모리를 더 절약할 수 있음. 

 

구간 트리의 초기화

구간 트리의 각 노드에 대해 위치 등을 저장해 두지 않는 것을 유의함. 해당 노드를 찾아가는 과정에서 표현하는 구간을 동적으로 계산할 수 있기 때문에 따로 저장해 둘 필요가 없음. 

struct RMQ {
	int n;
	vector<int> rangeMin;
	RMQ(const vector<int>& array) {
		n = array.size();
		rangeMin.resize(n * 4);
		init(array, 0, n - 1, 1);
	}
	int init(const vector<int>& array, int left, int right, int node) {
		if (left == right)
			return rangeMin[node] = array[left];
		int mid = (left + right)/2;
		int leftMin = init(array, left, mid, node * 2);
		int rightMin = init(array, mid + 1, right, node * 2 + 1);
		return rangeMin[node] = min(leftMin, rightMin);
	}
};

초기화 과정에 걸리는 시간 복잡도. O(n)임.

 

구간 트리의 질의 처리

교집합이 공집합인 경우

교집합이 [nodeLeft, nodeRight]인 경우

이 외의 모든 경우

트리의 바닦까지 최대 두 번만 탐색하므로, 전체 시간 복잡도는 여전히 O(logN)임

	int query(int left, int right, int node, int nodeLeft, int nodeRight) {
		if (right < nodeLeft || nodeRight < left) return INT_MAX;
		if (left <= nodeLeft && nodeRight <= right)
			return rangeMin[node];
		int mid = (nodeLeft + nodeRight) / 2;
		return min(query(left, right, node * 2, nodeLeft, mid), query(left, right, node * 2 + 1, mid + 1, nodeRight));
	}

 

구간 트리의 갱신

이 위치를 포함하는 구간은 트리에 O(lgN)개 있을 겁니다. 따라서 이들만을 재계산하면 O(lgN)시간에 구간 트리를 갱신할 수 있음. 

	int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
		if (index < nodeLeft || nodeRight < index)
			return rangeMin[node];
		if (nodeLeft == nodeRight) return rangeMin[node] = newValue;
		int mid = (nodeLeft + nodeRight) / 2;
		return rangeMin[node] = min(update(index, newValue, node * 2, nodeLeft, mid), update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
	}

 

예제: 특정 구간에서 최소치 두 개 찾기

구간 트리를 사용하려면 두 개의 작은 부분 구간에 대해 계산한 값을 효율적으로 합치는 방법이 있어야 함. 

 

예제: 정렬된 수열의 특정 구간에서 최대 출현 빈도 계산

이런 문제를 풀 때는 문제의 답만이 아니라 두 개의 답을 합치는 데 필요한 추가 정보도 계산해서 반환할 필요가 있음. 

struct RangeResult {
	int size;
	int mostFrequent;
	int leftNumber, leftFreq;
	int rightNumber, rightFreq;
};

RangeResult merge(const RangeResult& a, const RangeResult& b) {
	RangeResult ret;
	ret.size = a.size + b.size;
	ret.leftNumber = a.leftNumber;
	ret.leftFreq = a.leftFreq;
	if (a.size == a.leftFreq && a.leftNumber == b.leftNumber)
		ret.leftFreq += b.leftFreq;
	ret.rightNumber = b.rightNumber;
	ret.rightFreq = b.rightFreq;
	if (b.size == b.rightFreq && a.rightNumber == b.rightNumber)
		ret.rightFreq += a.rightFreq;
	ret.mostFrequent = max(a.mostFrequent, b.mostFrequent);
	if (a.rightNumber == b.leftNumber)
		ret.mostFrequent = max(ret.mostFrequent, a.rightFreq + b.leftFreq);
	return ret;
}