【学习笔记】线段树
线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶子节点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度未$O(\log n)$。而未优化的空间复杂度为$2N$，实际应用是一般还要开$4N$，的数组以免越界，因此有时需要离散化让空间压缩。
树的形态一般如下：（引用自OI-WIKI）
对于线段树中的每一个非叶子节点$[a,b]$，它的左儿子表示区间为$[a,\frac{a+b}{2}]$，它的右儿子表示的区间为$[\frac{a+b}{2}+1,b]$。因此线段树是平衡二叉树，最后的子节点数目为$N$，即整个线段区间的长度。
使用线段树可以快速查找某一个节点在若干条线段中出现的次数，时间复杂度为$O(\log 2n)$。而为优化的空间复杂度为$T(2N)$，因此有时需要离散化进行空间压缩。
图片举例（引用自CSDN la_alweq）
每个节点存什么，节点下标是什么，如何建树？
该数组为$a={1,8,6,4,3,5}$，红色代表节点存储的区间，蓝色表示该区间内的最大值。
每个叶子节点的值，就是数组的值，每个非叶子节点的度都为二，且左右两个孩子分别存储父亲一般的区间。
每个父亲存储的值也就是两个孩子存储的值的最大值。
如何快速找到非叶子节点的孩子以及非根节点的父亲？
对于一个区间$[l,r]$来说，最重要的数据当然就是区间的做右端点$l$和$r$，但是大部分的情况我们并不会去存储这两个数值，而是通过递归的传参方式进行传递。
这种方式用指针很好实现，定义两个左右子树递归即可，但是指针表示过于繁琐，而且不方便各种操作，大部分线段树都是使用数组进行表示，快速使用下标找到左右子树。
图片举例（引用自CSDN la_alweq）
其中的绿色是下表编号。
在最下排的编号从$9$直接到$12$，中间其实有两个空间。虽然没有使用，但还是存在。所以无优化的线段树开到$4N$才能防止RE。
每个父亲和孩子下标的关系如下：
- 每个左子树的下标都是偶数，右子树的下标都是奇数。
- 父亲节点是儿子节点的一半，向下取整。
- 儿子节点是父亲节点的两倍，或加一。
把线段树看作一个完全二叉树，空节点也当作使用。
根据奇怪的规律（不支持md所以省略）很简单就得到右子树节点为左子树节点数加一。
（这一段是什么用处呢？）
因为左子树都是偶数，所以我们常用位运算来寻寻找左右子树。
- k<<1，节点$k$的左子树下标。
- k<<1|1，节点$k$的右子树下标。
假如要修改$a[3]$，则包含此值的节点都需要更新。
根据二叉树的性质，$\log k$个节点都需要进行更新，这也正是为什么每次更新的时间复杂度为$O(\log n)$。
可以发现无论更新那个叶子节点，最终都会回到根节点，而把这个往上推的过程逆过来就是从根节点进行递归处理。
以下面的图为例（引用自CSDN la_alweq）
线段树的每个节点存储的都是一段区间的信息，如果刚好要查询这个节点，那么则直接返回这个节点的信息即可，比如直接查询$[1,6]$这个区间的最值，那么直接返回根节点信息$13$。
若要查询区间$[2,5]$，那我们只需要查询$[2,2]，[3,3]，[4,5]$，三个区间。$[4,4]，[5,5]$不需要查找，包含在$[4,5]$中了。
$[2,5]$一共五个区间，而且发现$[4,5]$这个区间已经包含了$[4,4]，[5,5]$两个子树的信息，所以需要查询的区间只有三个，是$[2,2]，[3,3]，[4,5]$。
可以通过更新的思路想出来查询的思路，从根节点开始往下递归，时间复杂度$O(\log n)$。
线段树的区间更新使用差分的思想。
传统上，对于区间$[l,r]$，可能每次都更新区间中的每个值，更新的复杂度将会是$O(n\log n)$，造成浪费。
在进行区间更新是，引用lazy标记，提高更新的效率。
如果当前区间被需要修改的目标区间完全覆盖，则在被更新节点上打lazy标记，此区间不向下传导，这样的搭配使区间更新的操作和区间查询类似，复杂度为$O(\log n)$。