티스토리 뷰
Index Tree 는 말 그대로 tree를 index로 관리하는 것을 의미한다.
즉, left, right child, parent 를 직접적으로 연결하지 않고, balanced binary tree 라는 가정 하에 수식으로 부모와 자식 index 를 계산한다.
Index Tree 는 이진 트리 역할을 하면서 주로 구간 최대값, 최소값, 구간합 등을 구할 때 사용된다.
이진 트리이므로 트리 전체를 만드는데는 O(N log N), 트리를 업데이트 하는데는 O(log N) 이 소요된다.
단순히 특정 구간의 최대, 최소, 합 등을 구할 때 O(M) (구간 길이 M) 이지만, 쿼리가 매우 많다면 O(QM) 이므로 이를 O(Q log M) 로 줄일 수 있다.
또한 기존 입력의 값이 수시로 업데이트 되어도 트리 업데이트 시에는 O(log N) 이 소요되므로
잦은 업데이트, 잦은 쿼리 시에 아주 유용하다.
Index Tree 구성은 다음과 같다.
1. 트리 만들기
입력으로 주어진 값이 N 개일 때, 입력의 첫 번째 값을 트리 마지막 depth 의 첫 번째 값으로 간주한다.
즉, 입력이 20개라면 int(log_2 20) = 4 이므로 4+1 = 5 depth 까지 존재한다. (depth 0 = root)
ex) 입력 20 개 일 때 tree의 index 구분
depth 0 : 1
depth 1 : 2 ~ 3
depth 2 : 4 ~ 7
depth 3 : 8 ~ 15
depth 4 : 16 ~ 31
depth 5 : 32 ~ 63
(그림판으로 대충 그린 그림.....)
입력 8개인 경우를 예로 들면,
검은 숫자는 기존 입력 index, 빨간 숫자는 tree의 index, 초록 숫자는 tree의 depth 이다.
이와 같이 balanced binary tree 인 환경에서는 굳이 child, parent 연결 없이 단순 계산으로 부모와 자식을 연결할 수 있다.
(그냥 index / 2 하면 부모)
최대값, 최소값, 구간합 경우 모두 tree 만드는 논리는 동일하다.
그냥 index / 2 하면 부모 노드이므로 index / 2 번째 값과 업데이트를 진행하면 된다.
이를 전체 리프 노드에 대해 진행하면 된다.
코드는 다음과 같다. (32는 예시로 input을 20개로 잡았기 때문에 tree 기준 index 계산 시 +32를 한 것 뿐)
void updateTree(int arrIdx)
{
// 트리 업데이트 하기
int treeIdx = 32 + arrIdx;
int num = arr[arrIdx];
while(treeIdx > 0) {
indexTree[treeIdx] = max(indexTree[treeIdx], num);
treeIdx /= 2;
}
}
구간합일 때 업데이트 하는 코드
void updateTree(int arrIdx)
{
// 트리 업데이트 하기
int treeIdx = 32 + arrIdx;
int num = arr[arrIdx];
indexTree[treeIdx] = num;
treeIdx /= 2;
while(treeIdx > 0) {
indexTree[treeIdx] = indexTree[2 * treeIdx] + indexTree[2 * treeIdx + 1];
treeIdx /= 2;
}
}
2. 입력 업데이트 하기
기존 배열의 값이 업데이트되어도 위 updateTree 에 동일하게 index 만 넣으면 되므로 생략한다.
3. 최대값, 최소값, 구간합 구하기
최대값, 최소값을 구하는 방식은 max, min 만 차이가 있으며, 구간합을 구하는 것도 sum을 할 것이냐 말것이냐의 차이이다.
그러므로 최대값인 경우로 설명을 하면 다음과 같다.
start ~ end 범위까지의 최대값을 구할 때,
start 가 짝수인 경우, 부모에 자신의 정보가 포함된 값이 기록되어 있으므로 바로 부모 노드로 간다.
(start = start / 2)
홀수인 경우, 부모에 left child 정보가 포함되어 있으므로, 자신과 최대값을 비교하여 업데이트 후, 옆 부모로 간다.
(start = (start + 1) / 2)
end 가 짝수 인 경우, 부모에 right child 정보가 포함되어 있으므로, 자신과 최대값을 비교하여 업데이트 후, 옆 부모로 간다.
(end = (end - 1) / 2)
홀수인 경우, 부모에 자신의 정보가 포함된 값이 기록되어 있으므로 바로 부모 노드로 간다.
(end = end / 2)
이에 대한 코드는 다음과 같다. (32는 예시로 input을 20개로 잡았기 때문에 tree 기준 index 계산 시 +32를 한 것 뿐)
int getMaxNumInRange(int arrStartIdx, int arrEndIdx)
{
// startIdx, endIdx : tree 기준
int startIdx = 32 + arrStartIdx;
int endIdx = 32 + arrEndIdx;
int res = 0;
// start index 짝수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (start / 2)
// start index 홀수 : 부모에 부모의 left child 정보 포함하여 기록 중
// 자신과 비교 후 (start + 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 짝수 : 부모에 부모의 right child 정보 포함하여 기록 중
// 자신과 비교 후 (end - 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 홀수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (end / 2)
// start <= end 일 때 동안 반복
while(startIdx <= endIdx) {
if(startIdx % 2 == 0)
startIdx /= 2;
else {
res = max(res, indexTree[startIdx]);
startIdx = (startIdx + 1) / 2;
}
if(endIdx % 2 == 0) {
res = max(res, indexTree[endIdx]);
endIdx = (endIdx - 1) / 2;
}
else {
endIdx /= 2;
}
}
return res;
}
구간합 구하기 코드
int getSumInRange(int arrStartIdx, int arrEndIdx)
{
// startIdx, endIdx : tree 기준
int startIdx = 32 + arrStartIdx;
int endIdx = 32 + arrEndIdx;
int res = 0;
// start index 짝수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (start / 2)
// start index 홀수 : 부모에 부모의 left child 정보 포함하여 기록 중
// 자신과 합한 후 (start + 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 짝수 : 부모에 부모의 right child 정보 포함하여 기록 중
// 자신과 합한 후 (end - 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 홀수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (end / 2)
// start <= end 일 때 동안 반복
while(startIdx <= endIdx) {
if(startIdx % 2 == 0)
startIdx /= 2;
else {
res = res + indexTree[startIdx];
startIdx = (startIdx + 1) / 2;
}
if(endIdx % 2 == 0) {
res = res + indexTree[endIdx];
endIdx = (endIdx - 1) / 2;
}
else {
endIdx /= 2;
}
}
return res;
}
따라서 전체 코드는 다음과 같다.
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
// 구간 최대값 구하기
int arr[20] = {0, }; // 기존 입력 값
int indexTree[64] = {0, }; // 인덱스 트리 값 (20개 입력 => depth 5 : 32개 => 전체 트리 : 1+2+4+..+32=63)
// 1번째 값이 tree의 root (depth 0)
void init()
{
for(int i = 0; i < 20; i++) {
arr[i] = rand() % 9 + 1;
}
// 길이 n 배열에 대해 인덱스 트리 만들기
// 전체 depth = int(log_2 n) + 1
// 20인 경우, log_2 20 = 4.xxxx
// depth : 0 ~ 5
// depth 0 : indexTree[1]
// depth 1 : indexTree[2:4]
// depth 2 : indexTree[4:8]
// depth 3 : indexTree[8:16]
// depth 4 : indexTree[16:32]
// depth 5 : indexTree[32:64]
// 마지막 depth 먼저 채우기
for(int i = 0; i < 20; i++) {
indexTree[32 + i] = arr[i];
}
}
void updateTree(int arrIdx)
{
// 트리 업데이트 하기
int treeIdx = 32 + arrIdx;
int num = arr[arrIdx];
while(treeIdx > 0) {
indexTree[treeIdx] = max(indexTree[treeIdx], num);
treeIdx /= 2;
}
}
int getMaxNumInRange(int arrStartIdx, int arrEndIdx)
{
// startIdx, endIdx : tree 기준
int startIdx = 32 + arrStartIdx;
int endIdx = 32 + arrEndIdx;
int res = 0;
// start index 짝수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (start / 2)
// start index 홀수 : 부모에 부모의 left child 정보 포함하여 기록 중
// 자신과 비교 후 (start + 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 짝수 : 부모에 부모의 right child 정보 포함하여 기록 중
// 자신과 비교 후 (end - 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 홀수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (end / 2)
// start <= end 일 때 동안 반복
while(startIdx <= endIdx) {
if(startIdx % 2 == 0)
startIdx /= 2;
else {
res = max(res, indexTree[startIdx]);
startIdx = (startIdx + 1) / 2;
}
if(endIdx % 2 == 0) {
res = max(res, indexTree[endIdx]);
endIdx = (endIdx - 1) / 2;
}
else {
endIdx /= 2;
}
}
return res;
}
void printTree()
{
// depth 0
cout << "depth 0 : " << indexTree[1] << '\n';
// depth 1
cout << "depth 1 : ";
for(int i = 2; i < 4; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 2
cout << "depth 2 : ";
for(int i = 4; i < 8; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 3
cout << "depth 3 : ";
for(int i = 8; i < 16; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 4
cout << "depth 4 : ";
for(int i = 16; i < 32; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 5
cout << "depth 5 : ";
for(int i = 32; i < 64; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
cout << "\n================\n";
}
int main()
{
init();
for(int i = 0; i < 20; i++) {
updateTree(i);
}
// 초기 트리 출력
printTree();
// 범위에 대해 계산
cout << "5 ~ 10 : " << getMaxNumInRange(5, 10) << '\n';
cout << "\n================\n";
// 숫자 업데이트
int cnt = 2;
while(cnt--) {
int idx = rand() % 20;
arr[idx] = rand() % 99 + 1;
updateTree(idx);
printTree();
cout << "5 ~ 10 : " << getMaxNumInRange(5, 10) << '\n';
cout << "10 ~ 15 : " << getMaxNumInRange(10, 15) << '\n';
cout << "15 ~ 19 : " << getMaxNumInRange(15, 19) << '\n';
cout << "\n================\n";
}
}
결과
구간합 전체 코드
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
// 구간합 구하기
int arr[20] = {0, }; // 기존 입력 값
int indexTree[64] = {0, }; // 인덱스 트리 값 (20개 입력 => depth 5 : 32개 => 전체 트리 : 1+2+4+..+32=63)
// 1번째 값이 tree의 root (depth 0)
void init()
{
for(int i = 0; i < 20; i++) {
arr[i] = rand() % 9 + 1;
}
// 길이 n 배열에 대해 인덱스 트리 만들기
// 전체 depth = int(log_2 n) + 1
// 20인 경우, log_2 20 = 4.xxxx
// depth : 0 ~ 5
// depth 0 : indexTree[1]
// depth 1 : indexTree[2:4]
// depth 2 : indexTree[4:8]
// depth 3 : indexTree[8:16]
// depth 4 : indexTree[16:32]
// depth 5 : indexTree[32:64]
// 마지막 depth 먼저 채우기
for(int i = 0; i < 20; i++) {
indexTree[32 + i] = arr[i];
}
}
void updateTree(int arrIdx)
{
// 트리 업데이트 하기
int treeIdx = 32 + arrIdx;
int num = arr[arrIdx];
indexTree[treeIdx] = num;
treeIdx /= 2;
while(treeIdx > 0) {
indexTree[treeIdx] = indexTree[2 * treeIdx] + indexTree[2 * treeIdx + 1];
treeIdx /= 2;
}
}
int getSumInRange(int arrStartIdx, int arrEndIdx)
{
// startIdx, endIdx : tree 기준
int startIdx = 32 + arrStartIdx;
int endIdx = 32 + arrEndIdx;
int res = 0;
// start index 짝수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (start / 2)
// start index 홀수 : 부모에 부모의 left child 정보 포함하여 기록 중
// 자신과 합한 후 (start + 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 짝수 : 부모에 부모의 right child 정보 포함하여 기록 중
// 자신과 합한 후 (end - 1) / 2 노드로 index 변경 (옆 부모 노드로 이동)
// end index 홀수 : 부모에 자신 정보 포함하여 기록 중
// 바로 부모 노드로 index 변경 (end / 2)
// start <= end 일 때 동안 반복
while(startIdx <= endIdx) {
if(startIdx % 2 == 0)
startIdx /= 2;
else {
res = res + indexTree[startIdx];
startIdx = (startIdx + 1) / 2;
}
if(endIdx % 2 == 0) {
res = res + indexTree[endIdx];
endIdx = (endIdx - 1) / 2;
}
else {
endIdx /= 2;
}
}
return res;
}
void printTree()
{
// depth 0
cout << "depth 0 : " << indexTree[1] << '\n';
// depth 1
cout << "depth 1 : ";
for(int i = 2; i < 4; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 2
cout << "depth 2 : ";
for(int i = 4; i < 8; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 3
cout << "depth 3 : ";
for(int i = 8; i < 16; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 4
cout << "depth 4 : ";
for(int i = 16; i < 32; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
// depth 5
cout << "depth 5 : ";
for(int i = 32; i < 64; i++) {
cout << indexTree[i] << " ";
}
cout << '\n';
cout << "\n================\n";
}
int main()
{
init();
for(int i = 0; i < 20; i++) {
updateTree(i);
}
// 초기 트리 출력
printTree();
// 범위에 대해 계산
cout << "5 ~ 10 : " << getSumInRange(5, 10) << '\n';
cout << "\n================\n";
// 숫자 업데이트
int cnt = 2;
while(cnt--) {
int idx = rand() % 20;
arr[idx] = rand() % 99 + 1;
updateTree(idx);
printTree();
cout << "5 ~ 10 : " << getSumInRange(5, 10) << '\n';
cout << "10 ~ 15 : " << getSumInRange(10, 15) << '\n';
cout << "15 ~ 19 : " << getSumInRange(15, 19) << '\n';
cout << "\n================\n";
}
}
결과
'알고리즘' 카테고리의 다른 글
| C++ lower_bound, upper_bound (0) | 2024.06.22 |
|---|---|
| C++ map, set struct에 대해 만들기 (0) | 2024.06.22 |
| combination, permutation 정리 (0) | 2024.05.01 |
| KMP 알고리즘 정리 (1) | 2024.05.01 |
| Trie 정리 (1) | 2024.05.01 |