原本这两天在搞网络流的....但最近几次网赛多次遇到了线段树的题目...意识到线段树还是重要的...所以今天就初步的了解了线段树最简单的应用...单点更新...今天学习线段树主要是看NotOnlySuccess大牛的模板(http://www.notonlysuccess.com/?p=978).代码风格非常好...很适合初学线段树的来参考...网上的一些PPT也不错...一步一步动态描述线段树的算法过程...
线段树是一棵二叉树...其根节点是整个区间...其叶子节点是单位区间...每次修改和查询的时间复杂度都是O(logn)...线段树的主要操作是
build ( 建树...其中这个地方我和队友讨论过是不是可以省去这一步..直接都先清0..然后按照插入的方式一个个插入...但自己研究了build部分的代码发现这一步尽量还是不要省...因为其建树时的速度比插入要快一些..)...其中参数sp是指的当前这个节点在二叉树中的编号...不难推出其左孩子为2*sp...右孩子为2*sp+1..开始我写的build是int类...然后最后是 return sum[sp]=build(l,Mid,sp*2) + build(Mid+1,r,sp*2+1); 但会出错...原因是输入数据不一定是2的阶乘..也就是这棵二叉树不一定时满的...所以这样赋值会调用到不要的空间..返回就会错误...
..Insert(插入或者说更新单位区间的数据)..
Getsum( 得到一段区间的和或者是最大值之类的 )...
当然这只是线段树的最简单应用...其实关于单点更新的题目...用树状数组应该编程复杂度会更低..效率也差不多...但这里先当做是线段树的一个入门吧...
分享到:
相关推荐
线段树及其应用.ppt
ACM 程序设计:线段树-1.pdf
ACM 程序设计:线段树-p6.pdf
ACM 程序设计:线段树-p1.pdf
【数据结构】【B】线段树及其应用.doc
线段树 线段树acm.ppt
毕业设计-数据结构【b】线段树及其应用.doc
http://ybt.ssoier.cn:8088 信息学奥赛一本通(提高篇)测试数据\第4部分 数据结构(提高篇)\ 第3章 线段树 测试数据
讲解线段树基本应用,适合初学者下载使用!
。。。
基于Python的线段树实现与优化.pdf
线段树的结构 线段树是一棵二叉树,其结点是一条“线段”——[a,b],它的左儿子和右儿子分别是这条线段的左半段和右半段,即[a, (a+b)/2 ]和[(a+b)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a+1]。下图就是一...
线段树完全版,涉及到线段树的所有用法。 包括单点更新(增减,替换),区间求和,区间最值。 区间求最大值的位置。 成段更新(延迟标记,增减)。 离散化 扫描线
线段树+面积并
这个是有关线段树的一份讲义,很透彻清晰地讲解了线段树的相关事项,值得一看
一种简单的线段树的实现 ,基础功能比较完善
一个讲述线段树的好资料,这里主要是程序部分,希望对广大成员能够有所帮助
线段中点练习题.pdf
线段树_方泓杰.pdf