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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

2008年7月21日的笔记  

2008-07-21 16:25:25|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数据结构

┌────┬╭─┐──┐ ┐┌┌─╮
 ┌──┐│┌┬──┬┐┌┼│─┬┐
 │  ││ │  │  ││ │ 
 │  ││┌┼──┼┐ │╯─┼┘
 │  ││ │  │  ││─┼┘
 └──╯┘└╯  └╯╰┴└─┴┘

左偏树:

外节点:两个儿子不同时存在的节点
NPL:根距离子孙中最近外节点的距离;
永远满足:root.left.NPL>=root.right.NPL
左偏树的NPL<=log[N+1]-1


基本操作:合并
together(a,b)
step1:if(a.root>b.root)swap(a,b)
step2:together(a.right,b)

function merge(a,b)
if (a==NULL)return b;
if (b==NULL)return a;
if (a.root.key>b.root.key)swep(a,b)
a.right=merge(a.right,b)
if (a.right.NPL>A.left.NPL)
swap(a.left,a.right)
if (a.right==NULL)a.NPL=0;
else a.NPL=a.left.NPL+1
return a;
end function

常用操作
add(a,b):merge(a,b);
delete(a,b):b=merge(b.left,b.right);

 

合并的时间复杂度:loga+logb;

 

 

 

 


╭─┐──┐┌─┬┼─┐┌┌─┼─┐
┌┬──┬┐┌─┘┘└┐╯┌─┼─┐
 │  │ ┌────┐│┌─┼─┐
┌┼──┼┐├────┤ ──┼──
 │  │ └────╯ ──┼─┘
└╯  └╯└────╯└─╯│└╯

 

 

可以:合并两个集合
判断两个元素是不是在一个集合中

 


int father[datamax];
int findroot(int a){return father[a]==-1?a:father[a]=findroot(a);}
void union(int a,int b){if ((a=findroot(a))!=(b=findroot(b)))father[a]=b;}
int check(int a,int b){return findroot(a)==findroot(b);}

 

 

╭─  ┐╮┌─┌──┐ ┐   ┐
│ ┌─┼┘│ │  │└┼┌┐─┤
└┬  │ ├─╰  ┘╭┤││╮│
╭┘┌─┼┘├─┌──┐│├││││
└─ ┌┼╯┼─└─┌╯││╰┐└│
└─└╯╰┘└ ──╯┘└└└╰└╯


动态统计问题:
实现两个操作:
1.修改一个元素
2.求一个区间内元素的和

 

怎么办?


-朴素的数组模拟
-线段树
a[1..100]=a[1..50]+a[51..100]

一个二叉树,每一个节点表一个区间[p,r)
每一个叶子节点表一个单位区间
[p,r)=>
.left=[p,m)
.right=[m,r)
m=(p+r)/2;

 

不断的划分,直到[p,p+1)
左右的兄弟加起来=他爸
每一层的节点都是[1,n)的划分;

如何进行区间分解?
兵分两路:
visit(leftchild,b,e,data)
visit(rightchild,b,e,data)

 

如何使用线段树?


他自身没有任何数据;
我们要为每一个区间(节点)加入附加信息。

 

例子:求和问题

node.sum=node所代表的区间内所有的元素的和。
操作:
修改叶子:
只用修改他的直系祖先即可
查询:
分解区间,分别求和即可。


 

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

历史上的今天

评论

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

页脚

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