6
14
2016
0

【合集】线段树 #基本操作

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

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

 

 

 

Category: Segment Tree | Tags: 线段树 | Read Count: 207

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com