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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

线段树  

2016-02-03 22:17:50|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

线段树

       这个神奇的数据结构,使我们终于能够快速地查找一段数据的信息。总结一下,它的优越性就可以用两个形容词概括:

     1.快速的,查询速度只用logn

     2.暴力的,可以适用很多题目

 

下面看一个例子:

就是有n个数,每次找一段的最值,还可以修改其中一个数,甚至一段数,之后,再找最值,除了求最值,求和,统计个数什么的都可以用logn的速度求出,6666666……

 

分析:

是怎么做到的呢?都知道胜者树吧,就是每个结点记得都是左右子树的最大值。这样有个优势,就是在维护时沿着树的路径往上找就行了,当构造的是一个完全二叉树时,维护的速度是logn,树根记的就是最大值。可它做不到的是找一段的最值,而引进线段树的概念后,略加改装即可查询一段的最值。

 

模拟一下:

假如8个数,求一段的最值,可构造这样一棵二叉树:

      线段树 - 杨鸿飞 - 一个叫杨鸿飞的人的博客(注:跟原来不同,多要记一个范围)

我们假如找4-7这个区间,该怎么找呢

顺序:                1-8

             1-4           |             5-8

    1-2    |    3-4           5-6    |    7-8

       1-1 |2-2   3-3|4-4   5-5|6-6  7-7 | 8-8

 

蓝色结点为所经过的路径;红色结点为剪枝,更所求范围不沾边;绿色结点为所求范围的一段,是已知条件;灰色结点为没被搜索的路径;

 

这样子记住了范围,查询起来就可以剪枝。最坏时间是4logn,是非常快的。虽然看起来查询了许多次,小数据看不出优越性,大数据就明显很快。


这里详细说一下查询过程,四种情况:

线段树 - 杨鸿飞 - 一个叫杨鸿飞的人的博客

 其中要写得短,可以把2和4合并一下,统一当成包含这种情况


找一段最大值的程序: 

#include <iostream>

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)
{
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)
{
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)
{
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);
}//查询一段最值

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;
}
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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