一，什么是线段树？
-
线段树是怎样的树形结构?
线段树是一种二叉搜索树，而二叉搜索树，首先满足二叉树，即每个结点最多有两颗子树，并且是一颗搜索树，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。
-
线段树能够解决什么样的问题？
线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。对于线段树来说，每次更新以及查询的时间复杂度为O(logN)。
-
线段树和其他RMQ算法的区别
常用的解决RMQ问题有ST算法，二者预处理时间都是O(NlogN)
(详见ST算法解决BMQ问题详解)，而且ST算法的单次查询操作是O(1)，看起来比线段树好多了，但二者的区别在于线段树支持在线更新值，而ST算法不支持在线操作。
1. 静态的区间询问：ST表
ST算法解决RMQ问题详解(图文并茂,保证看懂)_rmq代码c++思路及模板-CSDN博客
2. 动态的区间询问：线段树/树状数组
详解树状数组_树状数组是连贯的吗-CSDN博客
静态指的是，数字 不会发生 改变
动态指的是，在 查询过程中，数字可能会发生一定程度的 修改
二,线段树的基本操作
建树
思路
首先，我们得先明白几件事情:
每个结点存什么
结点下标是什么
如何建树
下面我以一个简单的求一段区间的最大值来描述上面的三个概念。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/124774.html