인덱스트리(구간합 트리)
인덱스트리
인덱스트리는 세그먼트 트리에 비해 구현이 매우 간단하다는 특징이 있다.
인덱스트리를 활용하여 구한 합을 구하는 과정도 O(logN)의 시간 복잡도를 갖는다.
인덱스트리는 세그먼트 트리에 비해서 메모리 효율성이 높다.
처리과정
인덱스트리는 특정한 숫자의 마지막비트를 구해서 처리한다.
특정한 숫자의 마지막 비트 구하기
A가 14라고 할때 A를 비트로 표현하면 다음과 같다.
00000000 00000000 00000000 00001110
그리고 이것을 2의 보수를 이용해 -A로 만들어 준다면
11111111 11111111 11111111 11110010 이 된다.
이 둘을 AND연산 처리한다면
00000000 00000000 00000000 00001110
11111111 11111111 11111111 11110010
-----------------------------------------------
00000000 00000000 00000000 00000010
이렇게 되고 그럼 마지막 비트만이 남게 된다.
이러한 마지막 비트를 이용해서 트리구조를 만들 수 있다.
여기서 인덱스 16은 1-16의 구간합을 값으로 갖게 되고 15는 15를, 14는 13-14의 구간합을, 13은 13을
12는 9-12의 구간합을 값으로 갖게 된다.
12아래로도 같은 형태로 값을 갖게 되는데 각 인덱스에 대하여 마지막 비트를 '내가 저장하고 있는 값들의 개수'
로 계산하는 것이다.
마지막 비트를 이용해 처리하는데 12의 경우는 0000 1100이고 2의 보수로 처리하면 1111 0100이 된다.
그럼 이 둘을 AND연산 한다면 0000 0100 이 되므로 마지막비트는 4가 된다.
그럼 12는 4개의 구간의 합을 가질 수 있다는 것이고 12, 11, 10, 9의 합을 갖게 되는것이다.
만약 1-13의 구간합을 구한다고 한다면
이와같이 인덱스 8, 12, 13의 합을 구한다면 그게 1-13의 구간합과 같아진다.
처리과정은 원하는 구간합의 마지막 인덱스인 13으로 가는데 그럼 13은 마지막비트가 1이기 때문에 13의 값
하나만 갖게 된다. 마지막 비트가 1이었으니 아래로 하나만 내려가서 인덱스 12로 내려가게 되고
12는 4의 마지막비트를 갖고 있으니 인덱스 13의 값과 12의 값을 더하고 4 낮은 인덱스 8로 이동한다.
인덱스 8은 마지막비트가 8이니 1-8의 구간합을 갖고 있고 마찬가지로 13과 12를 더한값에 8의 값을 더해준다.
그럼 원하는 구간의 시작값인 1의 값까지 모두 합했으니 1-13의 구간합이 나온다.
특정 인덱스 수정
수정할때는 마지막 비트만큼 구간을 뒤로 이동하며 값을 수정하면 된다.
5를 수정한다면 5를 수정하고 마지막 비트가 1이기때문에 하나만 올라가 인덱스 6으로 넘어가 6을 수정한다.
6은 마지막비트가 2이기 때문에 8로 이동해 8을 수정하고 8은 마지막비트가 8이니 16으로 올라가 수정해주면 된다.
예제코드
#include <stdio.h>
#define NUMBER 7
int tree[NUMBER];
int sum(int i){
int res = 0; //결과정수
while(i > 0 { //i가 감소하면서 반복
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);
/*
5-7의 구간합을 구하려고 한다고 했을 때
1-7의 구간합을 구한 뒤
1-4의 구간합을 빼주면
5-7의 구간합과 같다.
*/
}
int main(void){
update(1, 7); //트리의 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); //update는 그냥 값만 넣어주는 것이 아닌 += 이므로 +3이 되는것.
printf("4부터 7까지의 구간합 : %d\n", getSection(4, 7));
system("pause");
}1부터 7까지의 구간합 : 33
인덱스 6의 원소를 +3만큼 수정
4부터 7까지의 구간합 : 19
이렇게 결과값이 출력되는 것을 확인할 수 있다.
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직