#9 인덱스 트리

인덱스 트리

트리 구조로 구간 합 구하기

-세그먼트 트리는 구현하는 과정이 복잡하고 어렵다는 점에서 구간 합을 더 쉽게 구할 방법이 필요하다.

-인덱스 트리는 구현이 매우 간단하다.

-인덱스 트리를 활용해 구간 합을 구하는 과정도 O(logN)의 시간 복잡도를 가진다.

-인덱스 트리는 세그먼트 트리에 비해서 메모리 효율성이 높다.

 

 

특정한 숫자의 마지막 비트 구하기

-특정한 숫자 A의 가장 마지막 비트를 구하고자 할 때는 A& -A를 구하면 된다.

 

ex) A가 14일 때 이를 비트 형태로 표현하면,

A = 00000000 00000000 00000000 00001110
-A = 11111111 11111111 11111111 11110010
A & -A = 00000000 00000000 00000000 00000010

 

이다.

 

마지막 비트를 이용해 트리 구조 만들기

-각 인덱스에 대해 마지막 비트를 '내가 저장하고 있는 값들의 개수'로 표현한다.

예를들어 14라면,  마지막비트는 2가 나오고, 이는 14가 13,14의 구간합을 가지고 있다로 해석된다.

 

코드예시

//1부터 N까지의 구간 합 구하기
#include <stdio.h>
#define NUMBER 7
int tree[NUMBER];
int sum(int i) {
	int res = 0;
	while (i > 0) {
		res += tree[i];
		// 마지막 비트만큼 빼면서 앞으로 이동
		i -= (i & -i);
	}
	return res;
}

//특정 인덱스 수정하기
void update(int i, int dif) {
	while (i <= NUMBER) {
		tree[i] += dif;
		// 마지막 비트만큼 더하면서 뒤로 이동
		i += (i & -i);
	}
}

//구간 합 계산 함수 구현하기
int getSection(int start, int end) {
	return sum(end) - sum(start - 1);
}

//사용하기
int main(void) {
	update(1, 7);
	update(2, 1);
	update(3, 9);
	update(4, 5);
	update(5, 6);
	update(6, 4);
	update(7, 1);
	printf("1부터 7까지의 구간 합: %d\n", getSection(1, 7));
	printf("인덱스 6의 원소를 +3만큼 수정\n");
	update(6, 3);
	printf("4부터 7까지의 구간 합: %d\n", getSection(4, 7));
	system("pause");
}

 

결과값