写在前面的话，我也只是新手，这篇博客仅仅为本人个人整理与复习所用，能力有限，错误是在所难免的！因此如发现错误还请指出一同学习！

索引

一、定义

二、基本结构

三、常见应用

求区间和

求区间最大元素

四、拓展

离散化

多lazy标记

dfs序

空间优化

区间合并

扫描线

主席树

RMQ

zkw

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，在实际的应用中往往要开到4N来避免越界， 因此有时需要离散化让空间压缩。

上方叙述引用自百度百科——线段树

https://baike.baidu.com/item/线段树/10983506?fr=aladdin

注意：有的时候划分左右子树区间的时候不一定是 [left, mid] 和 [mid+1, right]，也有可能是 [left, mid] 和 [mid, right]，后者可用于求平面矩阵交的面积或者立体交的体积这样的经典线段树问题（后面会提到），他们的最小单元是非零长度的区间而不是单点。

线段树，本质就是一棵树，树上存储的是区间的信息，我们构建这样一棵树，主要是用来查询区间信息，因为在树上进行查询的时间复杂度是优秀的log2N。

我们举一个非常无脑的例子，我们要求 1 2 3 4 5 这五个数字中的数字个数（什么？？你自己都说5个了，还要求啥），虽然完全可以不用线段树来完成这个傻傻的问题，不过这也是一种求区间的信息的问题，即 [1, 5] 这个区间中元素的个数。

图中红色的数字表示每个节点所保存的区间信息，在这里保存的就是区间中元素的个数。

构造出这颗线段树，不仅可以求出 [1, 5] 中的元素个数，其他所有区间的元素个数我们都可以得到，而且每次询问的时间复杂度都为 log2N。询问每次从根节点 1 开始，如果访问到的区间被包含在询问的区间 [a, b] 之中，那么直接加上该区间保存的数值并且返回，否则 if(a mid) 访问右孩子。

除了这种建树和 区间查询以外，我们还可以动态地修改区间信息，修改单点信息，查询单点信息，线段树相关的题目再怎么改造修改，最后还是基于这五种线段树的基本操作。

下面我们来说说线段树的结点：

看到这，发现left、right 以及 w 都好理解，可是 lazy 懒标记是什么？我们后面再讲。

​ 通常包含了初始化+输入原始数据两个步骤，有时只需要进行初始化即可。

​ 大致过程就是从根节点开始初始化到底部，在叶子节点存储区间的信息，然后逐级向上反馈，合并状态。

​ 已知单点的信息全部存储于叶子节点，因此类似于二分法，从根节点出发，每次选择一个子树进行递归，直到找到叶子节点，时间复杂度log2N。