인덱스 트리

2042 구간 합 구하기 : https://www.acmicpc.net/problem/2042

1. 인덱스 트리:

- 포화 이진트리 형태의 자료 구조

- 리프 노드 : 배열에 적혀있는 수 (제일 아랫단 노드들)

- 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합

tree[i] = tree[i*2] + tree[i*2+1];

2. 트리의 기본

int tree[n];

루트부터 노드 index를 1이라고 한다면,

- 루트 -> 왼쪽 자식노드 : root idx * 2

- 루트 -> 오른쪽 자식노드 : root idx * 2 + 1

- 자식노드 -> 루트 : leaf idx / 2

3. 인덱스 트리에서 구간의 합을 구하는 쿼리 수행 방법

- start index : 해당 노드 index가 홀수일 경우 확인

- end index : 해당 노드 index가 짝수일 경우 확인

            //구간 합: b~c 값들의 합

            int start = nidx+b-1;

            int end = nidx+c-1;

            long long int sum=0;

            while(start <= end){

                if(start%2 == 1) sum += tree[start]; //왼쪽 index는 홀수일 경우 확인

                if(end%2 == 0) sum += tree[end]; //오른쪽 index는 짝수일 경우 확인

                start = (start+1)/2;

                end = (end-1)/2;

            }

            cout << sum << "\n";

4. 초기 트리 구성

: 제일 밑단 리프노드들이 1,000,000개일 때, 사이즈를 넉넉하게 *4 함.

long long int tree[1000000*4];

5. 트리 변화량 갱신

long long int delta; // 변화량

// 자신과 조상노드들에게 모두 변화량을 적용

while(node > 0){

    tree[node] += delta;

    node /= 2;

}