개념

이진 트리 중 하나로 구간 합을 구하는데 사용된다. 말단 노드에는 원소들이 들어 있고 부모는 자식들의 합이 된다. 부모는 모든 자식들의 합이 되기 때문에 연속되는 구간의 합을 구할 수 있다. 또한 특정 위치의 값을 지속적으로 바꿔야하는 경우에도 사용된다.

https://blog.hexabrain.net/246 참고

조건

• 부분 합을 계속해서 구해야 한다.
• 특정 인덱스 변경이 지속적으로 일어 날 수 있다.

사용 하면 좋은 경우

1. 부분 합을 계속 구해야 하는 경우
   • list에서 부분 합 배열을 구하는 경우 O(MN)의 시간이 필요하지만 Index Tree를 이용 할 경우 O(MlogN)의 시간으로 단축 시킬 수 있다.
2. 특정 인덱스의 변경이 지속적으로 일어 날 경우
   • 부분 합 배열에서 특정 인덱스를 고칠 경우 그 인덱스를 포함하는 모든 합을 다시 구해야 하기 때문에 O(MN)의 시간이 필요한데 Index Tree를 이용 할 경우 O(MlogN)으로 시간을 단축 시킬 수 있다.

구현 방법

기본 이진 탐색

1. 트리 사이즈 정하기

tydef long long ll;

ll getIndex(int num) { //num은 원소의 갯수
    ll tmp = 1;
    while(tmp < num) {
        tmp <<= 1;
    }
    return tmp * 2;
}

트리의 말단 노드에 모든 원소를 배치해야 하고 부모까지 배치해야하기 때문에 트리 배열의 사이즈는 $2^n$ ≥ (원소의 개수) 가 되는 n을 찾고 그거의 2배를 해야 부모 노드 까지 배치 할 수 있다.

1. 노드 값 채우기

ll index = getIndex(n);
ll p = index/2;
for(int i = 0; i < n; i++) { //말단 노드에 원소 입력
    scanf("%lld", &t[p]);
    p++;
}
for(ll i = (index/2) - 1; i > 0; i--) {
    t[i] = t[i*2] + t[i*2 + 1]; //왼쪽 자식과 오른쪽 자식의 합
}

트리의 말단 노드에 원소들을 입력 받고 부모 노드들에 자식들의 합을 대입한다. 부모 노드는 아래에서 부터 대입해야 한다.

b 위치의 값을 c로 바꾸기