线段树——HDU - 1754 ,
辣鸡学线段树中。。。。。。感觉很神奇
预备知识:
1:线段树是一种二叉搜索树,它从上至下逐步将一个大区间划分成一些更小的单元区间,每个区间对应线段树中的一个节点:
2:树中的每个节点代表着一段区间[L,R],每个节点(除叶子节点)的左儿子代表的区间为[L,mid],右儿子则为[mid+1,r]。可以发现对于一个节点来说,左右儿子所代表的区间加起来正好为当前节点的区间
3:叶子节点的所代表的长度为1,根节点代表的区间为整个序列区间
给个实例
线段树是建立在线段的基础上,每个结点都代表了一条线段[l,r]。长度为1的线段称为元线段。非元线段都有两个子结点,左结点代表的线段为[l,(l + r) / 2],右结点代表的线段为[((l + r)/2)+1,r]。
长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。
线段树的性质:
从图中我们可以看到,从根出发,到任意一个节点的距离为logn
对于任意一个区间[L,R],我们可以把它划分为logn个存在于线段树中的区间
比如[5,8]我们可以划分为[5,5]和[6,8]对于此线段树维护的序列中的每个元素来说,他都被包含在logn个存在于线段树的区间中,而且这些区间构成一条从根到叶子的路径,同时这个叶子必然代表的是这个元素本身
例如“5”这个元素被包含在[1,10]、[1,5]、[4,5]、[5,5]这几个区间内。
有时候我们经常会碰到一些跟区间有关的问题,而这些问题往往是建立在一个序列上,每次询问这个序列的某个区间[L,R]的某些信息,同时经常会带有修改操作,这个操作可能是区间修改,也可能是点修改
比如询问一个序列中[L,R]的最值,或者把[L,R]整体加v
我们可以将这类问题归为以下四种形式:
区间询问 区间修改 点修改 点询问
首先我们来讨论怎么构建初始状态的线段树
构建之前我们应该要先考虑需要维护的信息有哪些。很重要,维护的信息是我们线段树最重要的一个环节。
我们这里以维护最大值为例如
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
Output对于每一次询问操作,在一行里面输出最高成绩。Sample Input
5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5Sample Output
5
6
5
9
HintHuge input,the C function scanf() will work better than cin
这里就是维护一个最大值。
#include<cstdio>
#include<cstring>
#define maxl 200010
int n,m;
int a[maxl];
struct node{int l,r,maxnum;}
tree[maxl<<2];//存放节点的结构体数组。
char ch[2];
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void build(int k,int l,int r)//建树。用递归的思想,把我们需要维护的信息输入进去,比如这里的maxnum
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
tree[k].maxnum=a[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);//递归生成左右子树
tree[k].maxnum=max(tree[k<<1].maxnum,tree[k<<1|1].maxnum);
}
void prework()
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(tree,0,sizeof(tree));
build(1,1,n);//调用build函数生成线段树。
}
void change(int k,int d,int x)//更新操作。由于更新了一个节点的值会导致其他节点的值也改变
{
if(tree[k].l==tree[k].r && tree[k].r==d)//找到目标节点更新内容,
{
tree[k].maxnum=x;
return;
}
int mid=(tree[k].l+tree[k].r)>>1;
if(d>=tree[k].l && d<=mid)
change(k<<1,d,x);
else
change(k<<1|1,d,x);
tree[k].maxnum=max(tree[k<<1].maxnum,tree[k<<1|1].maxnum);//由于变化导致其他的值也改变了。
}
int query(int k,int l,int r)//查询操作,从头开始一层一层的向下找。注意一下当一个区间横跨了两个区间时候的情况,取最大值
{
int maxnum;
if(tree[k].l==l && tree[k].r==r)
return tree[k].maxnum;
int mid=(tree[k].l+tree[k].r)>>1;
if(r<=mid)
maxnum=query(k<<1,l,r);
else
if(l>=mid+1)
maxnum=query(k<<1|1,l,r);
else
maxnum=max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
return maxnum;
}
void mainwork()
{
int d,x;
for(int i=1;i<=m;i++)
{
scanf("%s%d%d",ch,&d,&x);
if(ch[0]=='Q')
printf("%d\n",query(1,d,x));
else
change(1,d,x);
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
prework();
mainwork();
}
return 0;
}