浅谈线段树

前置芝士：线段树。

例题 on Luogu：P3372 线段树 1

线段树简介

线段树是一种非常实用且用途广泛的数据结构，常用于区间修改+区间查询，多种算法的优化工具。在更高级的题目中，经常会用到这种数据结构。

线段树结构

如图是一颗基本的线段树。

其中 $[l,r]$ 表示此节点的值为 $a_l,a_l+1\dots a_r$ 的和。

接下来我们给线段树上每一个节点进行编号：

这时，你会发现：如果一个节点的编号为 $p$，那么他的左儿子的编号为 $2p$，右儿子为 $2p+1$。

线段树构建

我们目前要在一个长度为 $8$ 的数组 $a$ 上建线段树。可以思考：假如当前的节点在线段树中编号为 $p$，表示的区间为 $[l,r]$，那么会有两种情况：

• $l=r$，可以直接将当前节点 $p$ 赋值为 $a_l$，因为这个节点只包含这一个数；
• $l<r$，此时需先处理它的两个子节点：令 $mid=\frac{l+r}{2}$，可得左子节点范围为 $[l,mid]$，右子节点范围为 $[mid$