【c++提高1】数据结构之线段树详解_c++线段树

大纲

1.线段树思想

2.普通线段树操作函数

3.存储线段树

4.普通线段树操作实现

5.线段树常见搭配方式

6.进阶线段树-乘法线段树

7.进阶线段树-根号线段树

8.线段树解决问题

1.线段树思想

$线段树定义$

$线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。$

$线段树的思想是将一个区间[1,n]划分成两个区间：$
$[1,n/2]和[n/2+1,n]，接下来继续划分：$
$[1,n/4],[n/4+1,n/2]和[n/2+1,n/2+n/4-1],[n/2+n/4,n]$
…

$这个时候你就会发现划分出的每一个区间，就是一个树的节点，所有的区间构成了一棵树，它就称为线段树。$
$线段树是一个二叉树。$

$示例：n=8$

2.线段树操作函数

1.pushup函数

$将子节点的值传输到他们的父节点上，tr[p]表示的是p整棵子树的结果，所以子节点的计算结果就是整棵子树的结果，有点像前缀和的思想。$

2.pushdown

$如果父节点改变，相应的子节点也需要，pushdown函数就是实现将父节点改变信息的一个函数，也称为懒惰标记，就是给孩子节点传递信息。$

3.build

$比较核心的函数：将原来的整区间建立成线段树。就是实现线段树的建树过程，如上面的划分方式，是通过递归的方式不停划分两个区间，递归建立子节点(l,mid)和(mid+1,r)。$

4.modify

$修改函数，一般支持两种操作：单点修改，区间修改。分别需要使用函数pushup和pushdown辅助修改。单点修改的时候因为单点改变，所以所有祖先即改变，所以递归调用不停update(pushup+手动更新)。$

5.query

$查询函数，查询一段区间的结果，递归调用，找到答案所在位置，或者分解成多个目标求解，最后返回答案。$

3.存储线段树

1.线段树的儿子存储

$因为每一个节点都表示一个区间，显然不能用区间作为下标来存储左右儿子（有可能可以直接存左右儿子地址），所以可以给每一个节点编一个编号，设做儿子为当前节点编号\ast 2，左节点为当前节点编号\ast 2+1，常见的使用数组存储二叉树的方式。$
根节点的编号为1，接下来顺序编号即可。

2.线段树的节点信息存储
$定义一个结构体，里面存储改节点信息和当前这个节点所管辖的区间的左右端点。$

struct Tree{
    
	int val;
	int l,r;
} tr[maxm<<2];
1
2
3
4
5

结构体存储线段树，别忘了数组开4倍。

4.线段树函数实现

1.建树函数build
$递归建树。$
$怎样判断当前节点是叶子节点呢？$

$可以发现叶子节点肯定是不能划分了，所以它所管辖的区间长度一定是1。所以判断是否l,r是否相等即可。$

bool is_leaf(int l,int r)