Ryan_<

线段树基本操作题，之前做过，现在再复习一下。（其实是之前的代码没有保存好囧）

1、线段树中的区间l，r为序列的编号，k在序列中无实际意义。

2、结构体保存的是一段连续区间，即线段树中的节点，只需要记录s或mx，而不记录单点权值，这是特点也是便利之处。

1）单点修改，区间查询。

hdu1166 敌兵布阵

struct seg{int l,r,s;}t[N<<2];
int n,a[N];
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
void pushup(int k)
{
//	int l=t[k].l,r=t[k].r;
//	t[k].s=t[l].s+t[r].s;
		t[k].s=t[k<<1].s+t[k<<1|1].s;
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r){t[k].s=a[l];return;}//注意,是t[k]
	int mid=l+r>>1;//首先要定义mid!
	build(lson);build(rson);
	pushup(k);
}
void modify(int k,int pos,int delta)
{
	int l=t[k].l,r=t[k].r;
	if(l==r){t[k].s+=delta;return;}//注意,是t[k]
	int mid=l+r>>1;
	if(pos<=mid) modify(k<<1,pos,delta);
	else modify(k<<1|1,pos,delta);
	pushup(k);
}
int query(int k,int lx,int rx)
{
	int l=t[k].l,r=t[k].r;
	if(lx<=l&&r<=rx) return t[k].s;
	int mid=l+r>>1,ans=0;
	if(lx<=mid) ans+=query(k<<1,lx,rx);
	if(rx>mid) ans+=query(k<<1|1,lx,rx);
	return ans;
}
char opt[10];
int main()
{
	int tt=read();
	F(kase,1,tt){
		printf("Case %d:\n",kase);
		n=read();
		F(i,1,n) a[i]=read();
		build(1,1,n);
		while(1){
			scanf("%s",opt);
			if(opt[0]=='E') break;
			int x=read(),y=read();
			if(opt[0]=='A') modify(1,x,y);
			if(opt[0]=='S') modify(1,x,-y);
			if(opt[0]=='Q') printf("%d\n",query(1,x,y));
		}
	}
	return 0;
}

hdu1754 I Hate It

多组询问&&多组数据，跳坑了。。

struct seg{int l,r,mx;}t[N<<2];
int n,m,a[N];
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
void pushup(int k)
{
		t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r){t[k].mx=a[l];return;}
	int mid=l+r>>1;
	build(lson);build(rson);
	pushup(k);
}
void modify(int k,int pos,int x)
{
	int l=t[k].l,r=t[k].r;
	if(l==r){t[k].mx=x;return;}//直接覆盖
	int mid=l+r>>1;
	if(pos<=mid) modify(k<<1,pos,x);
	else modify(k<<1|1,pos,x);
	pushup(k);
}
int query(int k,int lx,int rx)
{
	int l=t[k].l,r=t[k].r;
	if(lx<=l&&r<=rx) return t[k].mx;
	int mid=l+r>>1,ans=0;//-inf
	if(lx<=mid) ans=max(ans,query(k<<1,lx,rx));
	if(rx>mid) ans=max(ans,query(k<<1|1,lx,rx));
	return ans;
}
char opt[5];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
	mec(t,0);
	F(i,1,n) a[i]=read();
	build(1,1,n);
	while(m--){
		scanf("%s",opt);
		int x=read(),y=read();
		if(opt[0]=='Q') printf("%d\n",query(1,x,y));
		if(opt[0]=='U') modify(1,x,y);
	}
}
	return 0;
}

2)成段更新

3)区间合并

poj3667 Hotel

给定一个01序列，两种操作：

①1 x：找到编号最小的长度为x的连续0区间(输出区间的左端点)，并将该区间赋值为1.

②2 x y：将区间[x,x+y-1]赋值为0.

这是线段树的另外一个经典操作，与之前所维护区间的数值不同，线段树中每个节点在这里维护的是对应区间内最长连续0区间(lsum左端点开始最长长度,rsum右端点开始最长长度,sum当前区间最长长度)。pushup即为区间的合并，pushdown即为区间修改标记的下传。

这篇讲得太好了！（并且惊现st评论~

http://www.cnblogs.com/scau20110726/archive/2013/05/07/3065418.html