一、概念

• 线段树是用一种树状结构来存储一个连续区间的信息的数据结构。

• 它主要用于处理一段连续区间的插入,查找,统计,查询等操作。

• 复杂度： 设区间长度是 $n$，所有操作的复杂度是 $logn$ 级别。

二、基本操作

2.1、建树

线段树上每个结点对应的是序列的一段区间，根结点对应的是整个区间 [1,n]。若一个结点对应的区间为 [l,r]，当 l = r 时，为叶子结点；当 l ≠ r 时，结点一定有左右儿子，令 mid = (l + r) / 2，左儿子对应的区间为 [l,mid]，右儿子对应的区间为 [mid + 1,r]。

void build(int l , int r , int k)
{
   
	if(l == r)
	{
   
		/*
		根据题意，给叶子结点赋值
		*/
		return; 
	}
	int mid = (l + r) >> 1;
	build(l , mid , k << 1);
	build(mid + 1 , r , k << 1 | 1);
	/*
	根据题意，在回溯的时候更新每个结点的值,例如求区间最大值、和、极值差
	*/ 
}
int main()
{
   
	build(1 , n , 1);
}

注意：
①：
线段树第一层有 1 个结点，第二层有 2 个结点，依次类推，线段树中的结点数是：
n + n / 2 + n / 4 + ... + 2 + 1 = 2 * n - 1

线段树的数组不能只开到 2 * n 的级别，要开到 4 * n 的级别。
(线段树存的是区间，二叉树存的是点，所以线段树会出现许多结点空着的情况，如下图，结点[3] 的左右儿子空缺)

②：
令线段树的高度(层数)为 $h$ ，$h$ 只有 $O($