下标线段树

简介

“简介”章节摘自 OI-Wiki。

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息在很多时候可以认为是满足（幺）半群的性质的信息。

一个幺半群 $M=(S,\circ,e)$，其中 $\circ$ 为在集合 $S$ 上定义的二元运算符，幺半群具有以下性质：

• 封闭性：$\forall x \in S$ 和 $\forall y \in S$ 有 $x\circ y \in S$。
• 结合律：$\forall x,y,z \in S$ 有 $(x \circ y) \circ z=x \circ (y \circ z)$。
• 存在幺元：即 $\exists e \in S$ 满足 $\forall x \in S$ 有 $e \circ x=x$，$e$ 为左幺元；或 $x \circ e=x$，$e$ 为右幺元。

我们观察到线段树上的信息一般满足这样的性质，一些数域上的加法与乘法自然，考虑二元的 $\max(x,y)$ 运算，此时幺元为 $-\infty$ 也满足这样的性质（一般左右幺元相同时简称为幺元）。

线段树的构造

线段树的基本结构与建树

线段树将每个长度大于 $1$ 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

举例：$\mathrm{val}=\{11,12,13,14,15,16\}$

此处应有图片

void build(int u,int l,int r){
	//对原数组 a 的 l-r 范围建立线段树，当前节点为 u
	if(l==r){//长度为 1
		val[u]=a[l];
		return;
	}
	int m=(l+r)>>1;//一种更好的写法是 int m=l+((r-l)>>1);
	build(u<<1,l,m);//递归建立左子树
	build(u<<1|1,m+1,r);//递归建立右子树
	val[u]=val[u<<1]+val[u<<1|1];//pushup 操作
}

如果用堆式建树，对于一个长度为 $n$ 的数列，线段树的数组大小需要开到 $4n$。

有一种方法只需要大小为 $2n$ 的数组：

C++Copy
inline void Index(int l,int r){return l+r|l!=r;}

线段树的区间查询

一般地，如果要查询的区间是 $[l,r]$，则可以将其拆成最多为 $O(\log n)$ 个极大的区间，合并这些区间即可求出 $[l,r]$ 的答案。

此处以查询 $[l,r]$ 的区间和为例。

C++Copy
int query(int u,int l,int r,int ql,int qr){
	//[l,r] 为查询区间，[ql,qr] 为当前节点包含的区间，u 为当前节点的编号
	if(ql<=l&&r<=qr)return val[u];
	int m=(l+r)>>1,ans=0;
	if(ql<=m)ans+=query(u<<1,l,m,ql,qr);
	if(qr>m)ans+=query(u<<1|1,m+1,r,ql,qr);
	return ans;
}

线段树的区间修改与懒惰标记

一般地，如果要修改的区间是 $[l,r]$，则可以将其拆成最多为 $O(\log n)$ 个极大的区间，在这些区间打懒标记即可快速修改 $[l,r]$ 的值。当递归到懒标记所在节点的子树时，就将懒标记下传。

线段树的扩展版本

• 下标线段树的卡常版本——zkw 线段树，一种非递归的写法，但这种写法的使用范围稍窄。
• 如果下标范围过大，但操作数量不大，可以使用 动态开点线段树。
• 线段树也可以维护值域，即每个值的出现次数，这个叫做 值域线段树。
• 线段树也可以支持可持久化，这个叫做 可持久化线段树。
• 两个值域相同的线段树可以合并，这个操作叫做 线段树合并。

例题：线段树维护区间数字计算（区间加减乘除，区间求和，区间最值等）

例题：线段树维护区间数字计算（循环型的操作）

例题：线段树维护区间数字计算（位运算）

例题：线段树维护区间括号序列、0/1 串

例题：线段树维护区间集合

例题：线段树自身的性质

例题：线段树求解满足条件的子区间数量

例题：线段树实现区间数字判重

例题：线段树维护函数

例题：线段树上二分

例题：兔队线段树

例题：线段树维护分治结构

例题：线段树分治

例题：线段树优化建图

例题：动态开点线段树

参考资料

• 线段树详解 （原理，实现与应用）_岩之痕-CSDN博客_线段树
• 统计的力量——线段树全接触_张昆玮（下载链接已失效，请自行搜索）
• KI子线段树 / AKEE SegmentTree - DMoRanSky - 博客园