Indexed Tree

"구간을 저장하기 위한 트리" 중 하나로 이 외에도 Segment Tree와 Fenwick Tree가 있다.
Segment Tree로 풀 수 있는 모든 문제는 Indexed Tree로 풀 수 있다.

---

Indexed Tree 사용하는 문제

1. 부분합을 계속해서 구해야 할 때
2. 특정 index의 변경이 계속 일어날 수 있을 때

위의 두 조건이 모두 만족하는 문제

---

활용

구간의 대표값 구하는 경우
1. 합
2. 최대, 최소
3. GCD

---

Indexed Tree 구성

1. 완전 이진 트리로 구성 - 마지막 레벨은 노드가 왼쪽에 몰려있고, 마지막 레벨을 제외하면 포화이진트리(모든 노드의 자식이 2개) 구조
2. 부모 노드가 자식 노드들의 대표값
   ex) 구간합: 자식들의 합, 구간 최대값: 자식들 중 큰 값, 구간 최소값: 자식들 중 작은 값
3. Leaf 노드 개수는 data 개수보다 큰 2^N개
4. Leaf 노드의 첫번째 index는 Leaf 노드의 개수와 같음
5. Index tree 공간 = Leaf 노드 개수 * 2

---

Indexed Tree 만들기

Leaf 노드의 첫번째 index 혹은 Leaf 노드 개수 구하기

for(B=1; B<N; B<<=1);	// B<<=1 는 B*=2와 같은 의미

---

수 변경

1. 변경하고자 하는 값 index 변경
   : index가 1부터 시작하면 Leaf 노드 첫번째 index-1을 더해주고, 0부터 시작하면 Leaf노드 첫번째 index를 더해줌
2. 부모로 이동 (index/2 혹은 index>>1)
3. 왼쪽 (index/2 혹은 index>>1), 오른쪽 (index/2+1 혹은 (index<<1)|1) 자식 값으로 부모 값을 갱신
4. 2-3을 root까지 반복 (결국 O(logN)만에 update 가능)

void update(int p, int v)
{
    p += (B-1);
    MinIDT[p] = v;
    while(p >>= 1)
    {
        MinIDT[p] = min(MinIDT[p<<1], MinIDT[(p<<1)|1]);
    }
}

---

구간 값 구하기

1. 구간 왼쪽(L), 오른쪽(R) 노드 index를 입력
2. 왼쪽(L), 오른쪽(R) 노드 index 값을 각각 변경
   : index가 1부터 시작하면 Leaf 노드 첫번째 index -1 을 더해주고, 0부터 시작하면 Leaf노드 첫번째 index를 더해줌
3. L이 홀수 일 경우 L번째 노드를 선택하여 구간 대표 값 갱신
4. L은 L+1 노드로 이동
5. R이 짝수 일 경우 R번째 노드를 선택하여 구간 대표 값 갱신
6. R은 R-1 노드로 이동
7. L, R노드의 각각 부모로 이동 (L/2, R/2)
8. L>R이 될 때까지 3-7 반복 (결국 O(logN)만에 구간값 구하기 가능)

최솟값

int lgMin(int l, int r)
{
    l += (B-1); r += (B-1);
    int minV = INF;
    while(l<=r)
    {
        if((l&1)==1) minV = min(minV, MinIDT[l]);
        if((r&1)==0) minV = min(minV, MinIDT[r]);

        l = (l+1)>>1;
        r = (r-1)>>1;
    }
    return minV;
}

구간 합

int lgSum(int l, int r)
{
    l += (B-1); r += (B-1);
    int sum = 0;
    while(l <= r)
    {
        if((l&1) == 1) sum += IDT[l];
        if((r&1) == 0) sum += IDT[r];

        l = (l+1)>>1;
        r = (r-1)>>1;
    }
    return sum;
}

L: tree의 R일 때, 값 취함
R: tree의 L일 때, 값 취함