线段树基本题型总结

线段树解决序列上修改查询问题，可以完成下面三种操作：1、更新点查询区间；2、更新区间查询点；3、更新区间查询区间

涉及到更新区间（成段更新）时，有一个技巧lazy_tag，在线段树子树加上tag，表示这个子树包含某些性质或者要进行某些操作，不用立即访问到这个子树的叶子，只有当下一次仍需访问这个子树下的节点时才继续进行。lazy_tag技巧可以用于下面几个方面：

1、区间加一个数。(这里的加可以变为任何满足区间加法的操作，比如区间异或，区间求GCD）。
2、区间变为一个数。
3、区间最值。
4、给出01序列，区间取反。
5、区间最长连续1的序列。
6、区间最长子段和。

下面HDU 1698 Just a Hook 线段树则是一道成段更新的例题。

#include<stdio.h>
#include<string.h>
int n;
struct Tree{
	int s;
	int t;
	int colour;
}tree[270000];

void build(int s,int t,int id){
	tree[id].s=s;
	tree[id].t=t;
	tree[id].colour=1;
	if(s!=t){
		int mid=(s+t)>>1;
		build(s,mid,id*2);
		build(mid+1,t,id*2+1);
	}
}
void update(int id,int s,int t,int tem){
	if(tree[id].s==s && t==tree[id].t){
		tree[id].colour=tem;
		return;
	}
	if(tree[id].colour!=-1)
		tree[id*2].colour=tree[id*2+1].colour=tree[id].colour;
	int mid=(tree[id].s+tree[id].t)>>1;
	if(mid>=t)
		update(id*2,s,t,tem);
	else if(s>mid)
		update(id*2+1,s,t,tem);
	else{
		update(id*2,s,mid,tem);
		update(id*2+1,mid+1,t,tem);
	}
	if(tree[id*2].colour==tree[id*2+1].colour)
		tree[id].colour=tree[id*2].colour;
	else
		tree[id].colour=-1;
}
int query(int id,int s,int t){
	if(tree[id].colour!=-1)
		return (t-s+1)*tree[id].colour;
	int mid=(tree[id].s+tree[id].t)>>1;
	if(mid>=t)
		return query(id*2,s,t);
	else if(s>mid)
		return query(id*2+1,s,t);
	else{
		return query(id*2,s,mid)+query(id*2+1,mid+1,t);
	}
}
int main(){
	int T,t,i,tem,mm;
	scanf("%d",&T);
	for(t=1;t<=T;t++){
		scanf("%d%d",&n,&mm);
		build(1,n,1);   
		for(i=1;i<=mm;i++){
			int p,q,r;
			scanf("%d %d %d",&p,&q,&r);
			update(1,p,q,r);
		}
		printf("Case %d: The total value of the hook is %d.\n",t,query(1,1,n));
	}
}