1.基本概念

线段树是一种常用来维护 $\color{Maroon}区间信息$ 的数据结构

可以在 O(logn) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间的最大值，求区间的最小值）等操作

如下图所示，线段树是建立在区间基础上的树，树的每个节点都代表着一段区间【L，R】

在这里插入图片描述

对于每个段区间【L，R】来说，我们注意到

（1）若 L = R，说明这个结点只有一个点，那么它就是一个叶子节点

（2）若 L < R，说明这个节点代表的不止一个点，此时它就会有两个儿子

左儿子：区间【L，M】
右儿子：区间【M + 1，R】

其中 M = （L + R）/ 2

在实现时，我们考虑 $\color{CadetBlue}递归建树$ 。即，设当前根结点为 u

如果根结点管辖的区间长度已经为 1，则可以直接根据原数组a上相应位置的值初始化该节点
否则将该区间从中点处分割为两个子区间【L，M】，【M + 1，R】，并分别进入左右节点的递归建树，最后将两个子节点的信息pushup到父节点u

struct Node// 线段树结构
{int l, r;int sum;// 【l, r】的区间和}tr[4 * N];
void pushup(int u)// 将信息往上传递，在这里维护的是区间和
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}
void build(int u, int l, int r)
{if(l == r) tr[u] = {l, r, a[r]};else{tr[u] = {l, r}; // 注意此行，若不初始化，会TLEint mid = l + r >>1;build(u << 1, l, mid);// 左儿子build(u << 1 | 1, mid + 1, r);// 右儿子pushup(u);// 将信息传递给父节点}}

思考：为什么对于线段树的数组空间我们要开到4倍的 N呢？

如果采用堆式存储（ 2u 是 u 的左儿子， 2u + 1 是 u 的右儿子），若有 n 个叶子节点，则 tr 数组的范围最大为 $2^{\lceil{logn}\rceil + 1}$

容易知道线段树的深度是 $\lceil{logn}\rceil$ 的，则在堆式情况下叶子节点（包括没有用到的叶子节点）数量为 $2^{\lceil{logn}\rceil}$ 。

我们可以发现 $\frac{2^{\lceil{logn}\rceil + 1}}{n}$ 最大值在 $n = 2^x + 1 (x ∈ N_+)$ 时取到，此时节点数为

$2^{\lceil{logn}\rceil + 1 } - 1 = 2^{x + 2} - 1 = 4n - 5$ ，故我们可以直接开 4n 的 tr数组，减少计算时间

2.原理推导

$\color{Turquoise}(1) 区间查询 - - O(logn)$

$\color{skyBlue}1.若这个线段树区间被完全包括在目标区间里面，则直接返回这个区间的值$

在这里插入图片描述

if(tr[i].l >= l && tr[r].r <= r) // 线段树区间被完全包含
return tr[u].sum;

$\color{skyBlue}2.若这个线段树区间的左儿子与目标区间有交集，那么搜索左儿子$

在这里插入图片描述

int sum = 0;
if(l <= mid) sum = query(u << 1, l, r); // 与左儿子有交集

$\color{skyBlue}3.若这个线段树区间的右儿子与目标区间有交集，那么搜索右儿子$

在这里插入图片描述

int sum = 0;
// if(l <= mid) sum = query(u << 1, l, r); 与左儿子有交集
if( r > mid) sum += query(u << 1 | 1, l, r); // 与右儿子有交集

例如，如下图所示，如果要查询的区间为 【1，5】的和，那么可以直接获取Tr[1] 的值（15）即可

在这里插入图片描述

如果要查询的区间为【3，5】，此时就不能直接获取区间的值，但是【3，5】可以拆分成【3，3】和【4，5】，可以通过合并这两个区间的答案来求得这个区间的和

一般地，如果要查询的区间为【l，r】，则可以将其拆成至多为 O(logn)个极大的区间，合并这些区间即可求出区间【l，r】的答案

Code

int query(int u, int l, int r)// u 为父节点，区间【l，r】为目标区间
{if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;// 如果线段树区间被完全包括在目标区间里面int sum = 0;int mid = tr[u].l + tr[u].r >> 1;// 左儿子与目标区间有交集if(l <= mid) sum = query(u << 1, l, r);// 因为sum初始化为 0，所以不写 += 也可以//右儿子与目标区间有交集if(r > mid) sum += query(u << 1 | 1, l, r);return sum;
}

$\color{Turquoise}(2) 单点修改- - O(logn)$

单点修改，换句话说就是如何实现点更新，假使我们要将原数组 a[3] + 7 ，则更新后的线段树应该变成

在这里插入图片描述

也就是说，当我们更新原数组a[]某一个位置 x 的数值时，在线段树中包含此值的区间都需要被更新，那么有多少个节点需要更新呢，也就是最大要达到多深才完成全部区间的更新呢？根据二叉树的性质，容易知道线段树的深度是 $\lceil{logn}\rceil$ 的，故此每次更新的时间复杂度为O(logn)

对于每次的更新，我们发现，无论你更新的是哪一个节点，最终都会将信息pushup到根结点，而把这个往上推的过程逆过来就是 $\color{Orange}从根结点开始，找到左子树或者右子树中包含需要更新的叶子节点，自顶向下更新即可$ ，所以我们还是采用递归的方法实现线段树的点更新

Code

void modify(int u, int x, int v) // 根结点，插入的位置，插入的值
{if(tr[u].l == tr[u].r) tr[u].sum += v;else{int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u << 1, x, v);// 左子树包含需要更新的叶子节点else modify(u << 1 | 1, x, v); // 右子树包含需要更新的叶子节点pushup(u);}
}

3.初步总结

目前为止，我们就把最基本的线段树操作过了一遍，必须抓住 $\color{Red}四个核心函数$

$\color{Green}pushup~~\color{CadetBlue}(int ~u)$ ：用子节点信息更新当前父节点信息
$\color{Maroon}build ~~\color{CadetBlue}(int ~u,~int ~ l, ~ int~r)$ ：在一段区间上，初始化线段树
$\color{purple}modify~\color{CadetBlue}(int ~u,~int ~ x, ~ int~v)$ : 修改目标位置 x 的属性
$\color{Turquoise}query~~\color{CadetBlue}(int ~u,~int ~ l, ~ int~r)$ : 查询区间【L， R】的属性（max，区间和，min等等）