선분 트 리 인편

선분 수 는 데이터 구조 로 이 진 트 리 의 변종 이다.실질 적 으로 이 진 트 리 의 노드 에 구간 정 보 를 저장 하 는 것 이다.
그 기본 노드 구 조 는?

struct node
{
      int left,mid,right,data,lazy; //left,right,mid      ,data            (max、min、sum).lazy     ,     .
};

이 진 트 리 가 순서 표 에 저장 하 는 특징 을 통 해 알 수 있 듯 이 번호 가 rt 인 노드 의 왼쪽 아이 노드, 오른쪽 아이 노드 의 번 호 는 rt < 1 > 이다. 、rt<<1|1  .
두 번 째 특징 구간 은 l, r 의 구간 노드 의 왼쪽 아이 노드, 오른쪽 아이 노드 의 구간 은 ( l , mid ) 、( mid+1 , r ).
다음은 흔히 볼 수 있 는 선분 수 를 만 드 는 방법 이다.

void CreatTree(int rt,int l,int r)
{
	tree[rt].l=l,tree[rt].r=r;
	tree[rt].mid=(l+r)>>1;
	tree[rt].lazy=-1;  
	if(l==r){
<pre name="code" class="cpp">		scanf("%d",&tree[rt].sum);

return;}CreatTree(rt<<1,l,tree[rt].mid);CreatTree(rt<<1|1,tree[rt].mid+1,r);}
시간
 log n  새로운 시간 과 길 어 지지 만 역 추적 유지 구간 정 보 를 통 해 조회 할 때 도
log n.
두 번 째: 구간 업데이트 (매번 구간 을 모두 추가 하거나 빼 기)

 
 
 
  
  线段树除了创建函数,最重要的另外两个函数是更新函数、查询函数。 
 
根据更新函数的不同,我们分为三种：一、点更新. 二、区间更新. 三、区间覆盖.
 
  
 
我们来看第一种：点更新  (每次更改点的信息)
 
  
 
void change(int rt,int k,int v){
	if(tree[rt].l==tree[rt].r){    //        
		tree[rt].sum=v;
		return; 
	}
	if(k<=tree[rt].mid)change(rt<<1,k,v);
	else change(rt<<1|1,k,v);
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; //        .(   sum   ,         ）
}
  
세 번 째: 구간 덮어 쓰기 (매번 특정한 구간 을 모두 특정한 값 으로 변경 합 니 다) 색칠
void change(int rt,int l,int r,int step){
    if(l==tree[rt].left && r==tree[rt].right){
    	tree[rt].lazy+=step;
		return; 
	}
	tree[rt].sum+=step*(r-l+1);  //      (   sum   ,          )
	int mid=tree[rt].mid;
	if(r<=mid) change(rt<<1,l,r,step);
	else if(l>mid)change(rt<<1|1,l,r,step);
	else{
		change(rt<<1,l,mid,step);
		change(rt<<1|1,mid+1,r,step);
	}
}
  
조회 함수:
4. 567913. 이상 은 모두 sum 구 와 예 를 들 었 다.
선분 나무의 세 가지 함 수 는 대략 모판 이 이 렇 습 니 다.
void change(int rt,int l,int r,int v){
	if(tree[rt].lazy==v)return;  //           
	if(tree[rt].l==l && tree[rt].r==r){   //         .
		tree[rt].lazy=v;
		return;
	}
	if(tree[rt].lazy!=0){         //    lazy          .
		tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt].lazy;
		tree[rt].lazy=0;
	}
	if(l>tree[rt].mid)change(rt<<1|1,l,r,v);
	else if(r<=tree[rt].mid)change(rt<<1,l,r,v);
	else{
		change(rt<<1,l,tree[rt].mid,v);
		change(rt<<1|1,tree[rt].mid+1,r,v);
	}
}