hyeoneee's blog

세그먼트 트리는 인덱스트리를 탑다운으로 내리는것이다

나머지는 다 같다.

탑다운으로 내리는 것이기 때문에 구현은 재귀로 구현한다.

구간 Update 

s부터 e 까지의 구간을 cost만큼 update 해 준다.

// s,e : 찾아야할 구간 , l,r : 전체 구간 ( nLeaf 더해주어야함)
static void update( int s , int e , int node , int l , int r , int cost){ 
	if(r < s || e < l )  return ;  // 시작점과 끝점이 (찾으려고 하는 구간)이 전체 지점에서 벗어날 때 리턴
	if( s <= l && r <= e){  // 시작점과 끝점(찾으려고 하는 구간)이 전체 트리에서 딱 맞으면? 
		Tree[node] += cost ;  // 해당 노드에 cost를 더해주고 리턴 
		return;
	}
	
	int mid = ( l + r) / 2 ; 
	update(s , e , node *2 , l , mid , cost );
	update(s , e , node * 2 + 1 , mid+1 , r , cost );

}

점 Query

static void query(int idx){ // 부모의 자식의 수?
	int res = 0 ; 
	idx += nLeaf;
	
	while(idx >=1){
		res+= tree[idx];
		idx /= 2;
	}
	return res;
}