hyeoneee's blog

정말 중요한 인덱스 트리이다.

특징

1. 포화 이진 트리이다 

- 모든 트리가 꽉차 있는데 자식은 2개씩

2. 0번은 비운다 

- 자식을 내려갈때 *2 , *2+1 을 해주어야 하기 때문이다.

3. 최대 노드 10만, 20만 정도가 최대이다.

-> 이게 안되면 리라벨링 / 좌표 압축을 해주어야한다 

=> 값을 그대로 넣는것이 아니라 값의 순서로 넣어주는 것이다.

4. 세그먼트 트리는 탑다운방식 ( 재귀)

   인덱스 트리는 바텀업 방식 

응용

1. 구간의 최소값 

- 초기화 = MAX

2. 구간의 최대값

- 초기화 = 0

3. 구간합

- 초기화 = 0

4. K번째 값 찾기 *** 

값 update

해당 노드를 찾아서 트리를 위로 부모로 올라가면서 ( 나누기 2) 

루트가( 1) 이 될때까지 값을 업데이트 해준다.

해당 되는 cost를 직접 바꾸지않고 현재 노드와의 차이값을 구해

해당되는 차이 값을 더해준다.

static int N;
nLeaf = 1;
while(nLeaf < N){
	nLeaf <<= 1;
}
tree = new int[nLeaf * 2];

static void update(int i, int cost) { // 해당 인덱스의 값을 cost로 update 해준다
	int idx = nLeaf + i - 1;
	int diff = cost - tree[idx];
	while (idx >= 1) {
		tree[idx] += diff;
		idx /= 2;
	}
}

구간 합 구하기

구간합은 s에서부터 e까지의 노드의 값을 더해준다.

s가 e가 될때까지

시작점이 오른쪽이면 노드를 모두 포함 하고 있지 못하기 때문에 

부모 값을 활용 할수 없어 , 해당 노드를 res에 더해주고 

노드를 오른쪽으로 옮겨준다. 

종료 지점이 왼쪽에 있으면 부모값을 활용할 수 없어, 해당노드를 res에 더해주고 

종료지점을 왼쪽 옮겨준다.

static int query(int s, int e) { // s부터 e까지의 값의 부분합을 구해준다.
	int res = 0;
	s = nLeaf + s - 1;
	e = nLeaf + e - 1;
	while(s <= e) { //시작점 끝점이 서로 크로스 될때까지 반복
		if(s % 2 == 1) { //시작점이 오른쪽이면
		res += tree[s];
        	s++;
		}
		if(e % 2 == 0) { // 끝점이 왼쪽이면
		res += tree[e];
         	e--;
		}
		s/=2; e/=2;
	}
	return res;
} 

K번째 수 구하기

k 번째 값을 구하려면

idx가 위에서부터 찾는데 nLeaf가 있는데 까지 찾으면된다.

좌우 값을 비교해가면서 

k가 왼족 노드 값에 모두 포함되면? 왼쪽으로 이동하고

값이 걸쳐있으면? 왼쪽 노드 값만큼 빼주고 오른쪽으로 이동한다.

 static int search(int k) {// k번째 수 찾기
        int idx = 1; // 루트부터 시작
        while (idx < nLeaf) { // 위에서부터 찾는데 nLeaf 있는데 까지만 찾아도돼
            int l = idx * 2; //좌
            int r = idx * 2 + 1; //우
            if (k <= tree[l]) {  //k번째 값이 왼쪽에 모두 포함되면?
                idx = l; // 걍 왼쪽으로 이동
            } else {
                // 값이 걸쳐있으면? 오른쪽으로 이동해야해
                k -= tree[l]; // 값이 걸쳐있으니깐 , 왼쪽 트리값 빼주기
                idx = r;// 오른쪽이동
            }

        }
        return idx - nLeaf + 1;
    }