手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > 精彩文章 > 文章 当前位置: 精彩文章 > 文章

数据结构之差分数组与线段树

时间:2018-10-23    点击: 次    来源:网络    作者:佚名 - 小 + 大

 离线就是他输入的时候是一股脑输入,然后是输入完了直接输出结果、
在线就是他每输入完,就让你查询或者输出状态、

差分数组在对于每一个区间修改操作的时候,立即响应询问时,区间两头是加减只要两次,但是要输出区间内每个元素的时候,就要扫一遍区间,复杂度是On、

 如果是离线,那么在他操作的时候两头加加减减,最后在扫一遍。总体O n
但是在线,操作n次 ,每次操作都要输出状态,区间扫一遍On,n个操作后就变成n方了

所以在线的时候我们还是选择用线段树

离线的时候我们选择用差分数组(因为差分数组好实现!)

以下是差分数组



上一篇:关于等比数列求和公式需要注意的地方

下一篇:没有了

备案ICP编号  |   QQ:3558389921  |  地址:山东济南  |  电话:暂不提供  |  
Copyright © 2018 天人文章管理系统 版权所有,授权down1s.com使用 Powered by 55TR.COM