线段树学习笔记

刚刚学习了可持久化线段树,AC了洛谷上的模板题,来总结一波这个看似复杂的数据结构吧(其实一点也不难的,我这么弱都一遍写对了).

umm仔细想了想,就从基础的线段树开始吧.

考虑一类问题.给你一个序列,让你进行以下的操作:

  • 将区间$[l,r]$中的所有值加上$v$
  • 查询区间$[l.r]$中的所有值的和
  • 查询区间$[l.r]$中的所有值的积
  • 查询区间$[l.r]$中的所有值的最大值
  • 查询区间$[l.r]$中的所有值的最小值

甚至是像这样,还要你支持这样的操作:

  • 将区间$[l.r]$中的所有值乘上$v$
  • 查询区间$[l.r]$中的所有值的最大公约数

等等.这些操作都有这样的共同点:

  • 对区间进行操作或是查询
  • 可以由任意两个区间的结果迅速(一般是$O(1)$)计算出这两个区间合并后得到的新区间的结果

对于这样的问题,我们有一个非常强大的工具,就是线段树.线段树可以支持以上的所有操作,而且思路非常清晰,代码也很简洁(但是我太菜所以写不简洁也写不漂亮),其除初始化的所有操作的时间复杂度均为$O(log\;n)$(初始化的复杂度是$O(n)$).

线段树的实现思路

显然,在线性结构上实现区间的高速操作是不太现实的(据我所知),因此我们采用树状结构,利用分治的思想,将整个序列一分为二,再把得到的两个序列分别一分为二,直到得到的子区间长度为$1$,也就是只有一个元素时,停止划分.这样建立了线段树之后,操作时就可以按照区间的起始和终止点

umm…等着填坑.

本文标题:线段树学习笔记

文章作者:Snake

发布时间:2018年04月03日 - 22:04

最后更新:2018年06月07日 - 14:06

原始链接:https://snake.moe/2018/04/03/线段树学习笔记/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。