Index Tree

• 구간합 구하기
• Array를 활용한 Binary Tree
• 실제 데이터는 리프노드에 저장
• 내부 부모 노드에 하위 노드들의 구간합을 저장
• Update: 리프 -> 부모 -> 루트까지 모두 업데이트해줌
• Query: 시작~마지막 구간의 합 가져오기. 시작, 마지막 노드의 부모를 각각 계산해서 올라가다가 찾은 부모가 교차되는 경우 멈춤

0. N개의 데이터

1. leafNode 개수(leafCount) : N <= 2^K 인 K를 찾기

Tree의 높이는 logN
Tree의 사이즈는 2^K*2
완전 이진트리이기 때문에!
N이 100000인 경우 2^17이 약 13만, 2^18 = 262144 이므로
tree 배열의 사이즈를 대충 100000*3 정도로 설정하면 넉넉

leafCount = 1;
while(N > leafCount) {
    leafCount <<= 1;
}

2. 리프노드가 저장될 시작 Index(leafPointer) 는 2^(K-1)

leafNode는 인덱스가 2^(K-1)~2^(K-1)+N-1 구간에 들어간다.

tree = new int[leafCount * 2];
leafPointer = leafCount - 1;
for(int i=1; i<=N; i++) {
	// 데이터가 1~N의 자연수로 입력된다고 가정
	tree[leafPointer+i] = i;
}

3. 부모노드에 값 업데이트

leafPointer에서 왼쪽으로 하나씩 당기면서 그 이하의 childNode합을 업데이트

• 부모값 = 왼쪽자식 + 오른쪽자식

for(int i=leafPointer; i>0; i--) {
	tree[i] = tree[i*2] + tree[i*2+1];
}

4. Query(Sum)

left, right을 입력 받아 구간합을 리턴한다.
leftPointer, rightPointer가 교차되기 전까지

• 만약 rightPointer가 leftChild인 경우
  leftChild를 합에 더한 후 rightPointer를 왼쪽으로 한칸 이동
• 반대도 마찬가지

4-1. 실제 tree에서의 leftPointer, rightPointer 계산

leftPointer += leafPointer;
rightPointer += leafPointer;

4-2. 구간합 찾기

leftChild는 index가 짝수, rightChild는 index가 음수

while(leftPointer <= rightPointer) {
	if (leftPointer % 2 == 1) { //leftPointer가 rightChild인 경우
    		result += tree[leftPointer];
    		leftPointer++;
    	}
        if (rightPointer % 2 == 0) { //rightPointer가 leftChild인 경우
        	result += tree[rightPointer];
            	rightPointer--;
        }
        
        // 부모노드로~
        leftPointer /= 2;
        rightPointer /= 2;
}

5. Update

index와 value를 입력받아 트리 전체를 업데이트
leafNode에 값을 업데이트 하는 경우 부모노드부터 루트노드까지 업데이트

// 실제 index계산하기
i = leafPointer + index;
// 리프노드 업데이트 후
tree[i] = value;
// 부모노드로~
i /= 2;

while(i > 0) {
    tree[i] = tree[i*2] + tree[i*2+1];
    i /= 2;
}