Tree - GitDeveloperKim/DreamEach GitHub Wiki

static int solve(int a, int a_depth, int b, int b_depth){
        // 둘의 depth가 같아질 때까지 위로 올린다.
        if(a_depth > b_depth){
            while(a_depth != b_depth){
                a_depth--;
                a = parent[a];
            }
        }
        else if(a_depth < b_depth){
            while(a_depth != b_depth){
                b_depth--;
                b = parent[b];
            }
        }

        // 둘의 부모값이 같아질 때까지 위로 올린다
        while(a != b){
            a = parent[a];
            b = parent[b];
        }

        return a;
    }

 //find_depth(1,1) 루트가 1번 노드, 깊이 1
	public static void find_depth (int from, int depth) {
		d[from] = depth;
		
		for (int i = 0; i < mat[from].size(); i++) {
			int to = mat[from].get(i);
			if (d[to] == 0) {
				parent[to][0] = from; // 기저 배열 생성
				find_depth(mat[from].get(i), depth+1);
			}
		}
	}

	public static void make_parent ( ) {
		for (int j = 1 ; j < k; j++) {  // j먼저
			for (int i = 1; i<= N; i++) {  // i번
				parent[i][j] = parent[ parent[i][j-1] ] [j-1];// 점화식 적용
			}
		}
	}

int find_lca(int a, int b) {
    if (depth[a] < depth[b]) { // a가 더 깊은 노드가 되게
        int temp = a;
        a = b;
        b = temp;
    }

    // a의 depth를 b에 맞춘다
    int diff = depth[a] - depth[b];
    int m = 0;

    // 예를 들어 13만큼 올라가야 한다면 이것을 이진수로 표현, 1101(2)이므로 
    // 1인 곳을 탐색할 때 마다 sparse 테이블의 높이 값을 증가 시키면 된다
    while (diff) {
        if (diff & 1) {
            a = parent[a][m];
        }
        m++;
        diff /= 2;
    }

    int lca;

    // a와 b가 같다면 그것이 lca
    if (a == b) {
        lca = a;
    } else {
        for (int k = 15; k >= 0; k--) {
            if (parent[a][k] != parent[b][k]) {
                a = parent[a][k];
                b = parent[b][k];
            }
        }
        lca = parent[a][0];
    }

    return lca;
}

tree = new int [1 << (my_log(200_0000)+1)]; // 200_0000 리프노드의 최대갯수

static long init (int node, int start, int end) {
	if (start == end) {
		// leaf node
		return tree[node] = array[start];
	} else {
		// not leaf node
		return tree[node] = init (node*2, start, (start+end)/2) + init (node*2+1, (start+end)/2+1, end);	// init left child node and right child node 
	}
}

static long sum (int node, int start, int end, int left, int right) {
	if (left > end || right < start) {
		return 0;
	} 
	if (left <= start && end <= right) {
		return tree[node];
	}
	return sum (node*2, start, (start+end)/2, left, right) + sum (node*2+1, (start+end)/2+1, end, left, right);		
}

static void update (int node, int start, int end, int index, long diff) {
	if (index < start || index > end) 
		return;
	tree[node] += diff;	
	if (start != end) {
		update (node*2, start, (start+end)/2, index, diff);
		update (node*2+1, (start+end)/2+1, end, index, diff);
	}
}

public static int kth (int node, int start, int end, int k) {
	if (start == end) {
		return start; // 인덱스를 리턴
	} else {
		int mid = (start+end)/2;
		// 왼쪽 자식 노드보다 현재값이 크거나 같다면 우측 탐색해야함 
		if (k > tree[2*node]) {
                    // (k값은 왼쪽 구간합 + 오른쪽 구간합이므로) 오른쪽 구간을 탐색할때는 왼쪽 구간합을 빼줘야한다
		    return kth(2*node+1, mid+1, end, k-tree[node*2]); 
                }
		else // k<= tree[2*node] 
		{
        	     return kth(2*node, start, mid, k);
                }
	}
}