开启辅助访问 切换到宽版

精易论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

用微信号发送消息登录论坛

新人指南 邀请好友注册 - 我关注人的新帖 教你赚取精币 - 每日签到


求职/招聘- 论坛接单- 开发者大厅

论坛版规 总版规 - 建议/投诉 - 应聘版主 - 精华帖总集 积分说明 - 禁言标准 - 有奖举报

查看: 3766|回复: 3
收起左侧

[技术专题] 浅谈线段树

[复制链接]
发表于 2018-12-30 20:12:00 | 显示全部楼层 |阅读模式   湖北省襄阳市

导入:
考虑这样一个问题:
给出长度为n的序列,一共有m条cha询,每条cha询可能是下面两种中的一种:
1 l r cha询闭区间[l,r]的总和
2 l r k 把闭区间[l,r]的每一个数加上k
n,m均满足大于零不小于五十万

很容易想到下面这段代码:
  
变量名类 型静态数组备 注
序列整数型0
n整数型 
m整数型 
i整数型循环变量
l整数型 
r整数型 
k整数型 
答案整数型 
是否cha询总和逻辑型 
重定义数组 (序列, 假, n)
计次循环首 (n, i)
' 储存每个 序列[i]
计次循环尾 ()
计次循环首 (m, )
判断 (是否cha询总和)
' cha询总和
答案 = 0
变量循环首 (l, r, 1, i)
答案 = 答案 + 序列 [i]
变量循环尾 ()
' 加上k
变量循环首 (l, r, 1, i)
序列 [i] = 序列 [i] + k
变量循环尾 ()

计次循环尾 ()

这段代码思路非常清晰,它很好地模拟了每个操作,但是,太慢了
如果n和m都给个五十万,就没法一秒搞定了哦~
PS:本题可以用树状数组写。
怎么办呢,我们就想是不是可以稍微优化一下。
引入概念:差分与前缀和。
差分:数组的第一个元素储存第一个元素,后面的元素储存这个元素与上一个元素的差。
栗子:1 2 3 4 5 存差分后=> 1 1 1 1 1
好处:方便区间修改,例如将栗子中的前四个元素加上3,只需要第一个(1=0+1)加3,第五个(5=4+1)减3就行了,我们试一试:
1(+3) 1 1 1 1(-3) => 4 1 1 1 -2 化为原数列=> 4 5 6 7 5
果然很方便,但是从这个过程中也稍微感受到了差分的不方便之处:虽然区间修改很快,但是如果我要知道其中的一个数,就不方便了,需要从头一直加到想要的那个数那里。因此,区间cha询并没有优势。
相反,前缀和就不一样,它刚好相反,看看它的定义~
前缀和:数组的每个元素储存数列的第一个元素到这个元素的总和。
仍然用上面的栗子:
1 2 3 4 5 存前缀和后=> 1 3 6 10 15
好处:cha询区间和非常方便。例如cha询[2,4]的总和,就用第4个元素减去第1个:10-1=9。
原理:第一个元素储存的是sum{1},第四个则是sum{1,2,3,4},相减就是想要的sum[2,4]啦~
糟糕的地方:区间修改就没那么快了。很显然,我们需要循环修改,没有性能优势。
以上介绍的两种优化,感兴趣的朋友们可以自己尝试一下~
有了这么多铺垫,终于要导出我们今天的主角——线段树了。
线段树的确是一棵树。它的每个节点都储存着区间信息。
由于我突然懒得画图了,而没得图线段树又讲不成,就先鸽着吧,反正我至今也没能用易语言写出能用的线段树。

评分

参与人数 2好评 +2 精币 +8 收起 理由
Patek + 1 + 3 支持开源~!感谢分享
冰点 + 1 + 5 感谢分享,很给力!~

查看全部评分


结帖率:38% (3/8)
发表于 2019-2-12 20:23:39 | 显示全部楼层   广东省广州市
都是oier吧
回复 支持 反对

使用道具 举报

发表于 2019-1-24 00:43:32 | 显示全部楼层   陕西省西安市
谢谢楼主的分享
回复 支持 反对

使用道具 举报

结帖率:81% (63/78)
发表于 2019-1-1 01:02:28 | 显示全部楼层   广东省阳江市
没懂是什么东西 尴尬
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则 致发广告者

发布主题 收藏帖子 返回列表

sitemap| 易语言源码| 易语言教程| 易语言论坛| 易语言模块| 手机版| 广告投放| 精易论坛
拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论,本站内容均为会员发表,并不代表精易立场!
论坛帖子内容仅用于技术交流学习和研究的目的,严禁用于非法目的,否则造成一切后果自负!如帖子内容侵害到你的权益,请联系我们!
防范网络诈骗,远离网络犯罪 违法和不良信息举报电话0663-3422125,QQ: 793400750,邮箱:wp@125.la
Powered by Discuz! X3.4 揭阳市揭东区精易科技有限公司 ( 粤ICP备12094385号-1) 粤公网安备 44522102000125 增值电信业务经营许可证 粤B2-20192173

快速回复 返回顶部 返回列表