데이터 구조의 - 선분 트 리 (1)

선분 수 는 ACM 에서 흔히 볼 수 있 는 데이터 구조 로 모든 점 은 하나의 선분 [a, b] 을 대표 하고 길 이 는 1 의 원 선분 이 며 모든 잎 결점 의 길 이 는 1 이다.길이 범 위 는 [1, L] 의 한 선분 나무의 깊이 는 log (L - 1) + 1 이다.
    선분 트 리 의 기본 적 인 응용 시 특정한 단락 의 합, 최대 최소 값 을 조회 하고 세그먼트 업데이트 로 매번 작업 의 복잡 도 를 log (n) 로 확보 합 니 다.
    선분 수 에 관 한 글 이 많 으 니 참고 하 시기 바 랍 니 다 http://www.notonlysuccess.com/?p=59.
    여기 서 저 는 hdu 와 poj 위의 선분 트 리 에 관 한 간단 한 응용 을 예 로 들 어 설명 합 니 다.
hdu 1166 (단일 업데이트, 구간 구 화):
    적군 해안선 에는 n 개의 캠프 가 배열 되 어 있 으 며, 각 캠프 에는 몇 명의 병사 가 있 으 며, 각 캠프 의 병사 들 은 수시로 변동 (증가 또는 감소) 하고 있 으 며, 수시로 두 캠프 사이 의 병사 수의 합 을 구 해 야 한다.
    우선 구조 선분 나무의 구조:

struct Seg_Tree
{
	int left;//   
	int right;//   
	int value; //        
	int calmid()
	{
		return (left+right)>>1;
	}
}tt[MAX*4];//MAX     ，           4 

     그 다음 에 선분 트 리 만 들 기:

int build(int left,int right,int idx)//idx 1  
{
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right)
		return tt[idx].value = num[left];
	int mid = (left + right)>>1;
	return tt[idx].value = build(left,mid,LL(idx)) + build(mid+1,right,RR(idx));
}

     어떤 캠프 에 병사 가 증가 하거나 감소 하 는 경우 업데이트 작업 이 있 습 니 다:

void update(int id,int x,int idx)
{
	tt[idx].value += x;
	if(tt[idx].left == tt[idx].right)
		return;
	int mid = tt[idx].calmid();
	if(id <= mid)
		update(id,x,LL(idx));
	else
		update(id,x,RR(idx));
}

    어떤 캠프 의 병사 수 총 계 를 조회 하 세 요:

int query(int left,int right,int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
		return tt[idx].value;
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(mid < left)
		return query(left,right,RR(idx));
	else
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
}

  
hdu 1754 (단일 업데이트, 구간 최대 값):
    선생님 은 학생 a 에서 학생 b 까지 의 가장 좋 은 성적 이 얼마 인지 물 어 보 는 것 을 좋아 합 니 다. 그 사이 에 일부 학생 들 의 성적 도 바 꿀 수 있 습 니 다.
    선분 트 리 만 들 기:

int bulid(int left, int right, int idx)
{
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right)
		return tt[idx].value = num[left];
	int mid = tt[idx].calmid();
	return tt[idx].value = max(bulid(left,mid,LL(idx)), bulid(mid+1,right,RR(idx)));
}

     어떤 학생 의 성적 변경 에 대해 업데이트 작업 이 있 습 니 다. 

void update(int id, int value, int idx)		//   ，        :          ，       
{
	if(tt[idx].left == tt[idx].right)
	{
		tt[idx].value = value;
		return;
	}
	int mid = tt[idx].calmid();
	if(id <= mid)
		update(id,value,LL(idx));
	else
		update(id,value,RR(idx));
	tt[idx].value = max(tt[LL(idx)].value, tt[RR(idx)].value);
}

    어떤 단계 의 학생 성적 중 최대 치 를 조회 합 니 다.

int query(int left, int right, int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
		return tt[idx].value;
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(left > mid)
		return query(left,right,RR(idx));
	else
		return max(query(left,mid,LL(idx)), query(mid+1,right,RR(idx)));
}

 상기 두 가지 예 제 는 단일 업데이트 에 대해 세그먼트 업데이트 에 대해 hdu 1698 이 있 습 니 다.
    dota 안에 갈고리 가 있 는데 n 단 으로 구성 되 어 있 습 니 다. 처음에는 모두 구리 이 고 단락 당 무 게 는 1 입 니 다.지금 그 중에서 a - b 이 부분 을 금 이나 은 으로 바 꾸 려 고 합 니 다. (무 게 는 각각 3, 2) 이 갈고리 의 총 무 게 를 조회 해 야 합 니 다.
    선분 트 리 만 들 기:

void build(int left, int right, int idx)
{
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].value = 1;//       1,-1           （      ）
	if(left == right)
		return;
	int mid = (left + right)>>1;
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}

    a - b 세그먼트 의 갈고리 업데이트:

void update(int left, int right, int value, int idx)		//    
{
	if(left <= tt[idx].left && right >= tt[idx].right)
	{
		tt[idx].value = value;
		return;
	}
	if(tt[idx].value != -1)
	{
		tt[LL(idx)].value = tt[RR(idx)].value = tt[idx].value;
		tt[idx].value = -1;			//              
	}
	int mid = tt[idx].calmid();
	if(left <= mid)
		update(left,right,value,LL(idx));
	if(mid < right)
		update(left,right,value,RR(idx));
}

    어떤 갈고리 의 무 게 를 조회 합 니 다:

int query(int left, int right, int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
	{
		if(tt[idx].value != -1)
			return (right-left+1)*tt[idx].value;
		else
		{
			int mid = tt[idx].calmid();
			return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
		}
	}
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(left > mid)
		return query(left,right,RR(idx));
	else
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
}

 
선분 트 리 를 배우 고 선분 트 리 의 구 조 를 익히 고 찾 고 업데이트 해 야 합 니 다.