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

24.6 펜윈 트리: 빠르고 간단한 구간 합

구간 중 필요한 부분만 남긴 결과를 보여줌. 남은 구간은 수는 정확하게 n개임. 물론 n개의 수에 대한 부분 합을 n개의 숫자에 저장하는 것이니 놀랍지는 않지만, 구간 트리에 비하면 꽤 큰 절약임. 어떤 부분 합을 구한든 O(lgn)개의 구간 합만 있으면 된다는 사실. 각 구간에 대해 오른쪽 끝 원소의 인덱스와 이들의 이진수 표현을 보여줌. 다른 부분 합에 대해서 일일이 확인해 보면 오른쪽 끝 위치의 이진수 표현에서 마지막 비트를 지우면 다음 구간을 쉽게 찾을 수 있음. 펜윅 트리에서 배열의 값을 변경하는 것은 해당 위치의 값에 숫자를 더하고 빼는 것을 구현함. 맨 오른쪽에 있는 1인 비트를 스스로에게 더해 주는 연산을 반복하면 해당 위치를 포함하는 구간들을 만날 수 있음.

struct FenwickTree {
	vector<int> tree;
	FenwickTree(int n) : tree(n+1) {}
	int sum(int pos) {
		++pos;
		int ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos &= (pos - 1);
		}
		return ret;
	}

	void add(int pos, int val) {
		++pos;
		while (pos < tree.size()) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
};

이 두 연산 모두 시간 복잡도는 O(lgn)임. 펜윅 트리의 구현은 주석을 전부 포함해 30줄도 안 됨. 계속 변하는 배열의 구간 합을 구할 때는 구간 트리보다 펜윅 트리를 자주 씀.

 

24.7 문제: 삽입 정렬 시간 재기

이 정렬 과정에서 숫자들을 총 몇 번이나 옮기는지 계산하는 프로그램을 구현하시오.

 

24.8 풀이: 삽입 정렬 시간 재기

주어진 수열에서 반전의 수를 세는 좋은 방법으로 병합 정렬이 있음.