注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

线段树(程序+详解)  

2016-01-22 19:35:48|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include <iostream>
#include <algorithm>

using namespace std;

struct Tnode
{
int le,ri; //表示范围(le~ri)
int max; //范围最大值
int lc,rc; //左树位置,右树位置
};

Tnode f[100100];
int fp=0;
int oo=1<<31;

int Push(int l,int r,int x) //放入新结点
{
f[fp].le=l; f[fp].ri=r; f[fp].max=x;
fp++;
return fp-1;
}//用浮动数组实现

int Create(int l,int r) //创建一棵二叉树,l和r辅助递归
{
int now=Push(l,r,-oo);

if (l<r)
{
int mid=(l+r)>>1;
f[now].lc=Create(l,mid); //建立左树,顺便记录位置
f[now].rc=Create(mid+1,r); //建立右树 ,顺便记住位置
}

return now;
}//递归实现

void Update(int rp,int cp,int x) //维护线段树,把第cp个数改成x
/* 只用记结点位置即可知道许多有用的信息(rp为当前节点) */
{
int tl=f[rp].le , tr=f[rp].ri; //当前范围

if (tl>tr) return; //边界处理
if (cp<tl || cp>tr) return; //越界处理

if (tl==tr) { f[rp].max=x; return; } //找到要改变的点,更新

Update(f[rp].lc,cp,x); //递归左树
Update(f[rp].rc,cp,x); //递归右树

f[rp].max=max(f[f[rp].lc].max,f[f[rp].rc].max); //合并最大值

return;
}//由于没有记父亲结点,所以要先递归找到,再维护路径 (递归实现)

int Query(int rp,int l,int r) //查询区间l~r的最值,rp辅助递归
{
int tl=f[rp].le , tr=f[rp].ri; //当前范围

if (tr<l || r<tl) return -oo; //越界处理
if (l<=tl && tr<=r) return f[rp].max; //被包含的情况直接选

int mid=(tl+tr)>>1;
int lemax=-oo,rimax=-oo;

if (tl<=l && l<=mid) lemax=Query(f[rp].lc,l,r); //求左边最值
if (mid<r && r<=tr) rimax=Query(f[rp].rc,l,r); //求右边最值

return max(lemax,rimax); //选最大
}//递归实现
/* 这里实际含有四种情况1.越界;2.被包含3.一边包含,一边不含;4.全部包含 */

int main()
{
int n; cin>>n;
int root=Create(1,n);

int q; cin>>q;
for (int i=0; i<q; i++)
{
char ch;
cin>>ch;
if (ch=='C')
{
int p,x;
cin>>p>>x;
Update(root,p,x);
cout<<f[root].max<<endl;
}
if (ch=='F')
{
int l,r;
cin>>l>>r;
cout<<Query(root,l,r)<<endl;
}
cout<<endl;
}
}

  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018