线段树

参考资料

简介

线段树（Segment Tree）把区间递归二分，每个节点维护对应子区间的聚合信息（和、最值等），支持 $O(\log n)$ 的区间修改与区间查询。修改与查询都把目标区间拆成 $O(\log n)$ 个节点区间处理。区间修改用 懒标记（lazy tag）延迟下放：先把整段更新记在节点上，待访问子节点前再下传，避免逐元素修改。

实现

773 Bcpp
struct SEG
{
	ll a[N],val[N<<2],tag[N<<2];
	void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
	void push_up(int u){val[u]=val[ls]+val[rs];}
	void push_down(int u,int l,int r)
	{
		gx(ls,tag[u],mid-l+1);
		gx(rs,tag[u],r-mid);
		tag[u]=0;
	}
	void build(int u,int l,int r)
	{
		if(l==r){val[u]=a[l];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(u);
	}
	void update(int u,int l,int r,int x,int y,ll v)
	{
		if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
		push_down(u,l,r);
		if(x<=mid)update(ls,l,mid,x,y,v);
		if(y>mid)update(rs,mid+1,r,x,y,v);
		push_up(u);
	}
	ll query(int u,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return val[u];
		push_down(u,l,r);
		ll res=0;
		if(x<=mid)res+=query(ls,l,mid,x,y);
		if(y>mid)res+=query(rs,mid+1,r,x,y);
		return res;
	}
};

线段树合并 & 分裂

在动态开点的权值线段树上，线段树合并 把两棵树对应位置的节点递归合并成一棵：某一侧为空时直接返回另一侧，否则递归合并左右子树并上传。

合并的总复杂度与被合并掉的节点数同阶，因此把 $n$ 棵单点线段树两两合并的总代价为 $O(n\log n)$ 。配合 线段树分裂（按排名或值域拆出一棵子树）可支持更灵活的操作，常与树上差分结合处理路径加、子树查询等离线问题。

李超线段树

李超线段树 维护一组一次函数（线段），支持插入一条线段、查询某个横坐标处所有线段取值的最大（或最小）值。

每个节点记录「在该区间中点处最优」的那条线段；插入时与节点上已有线段比较，把较劣的一条递归下放到它仍可能更优的半区间。插入复杂度 $O(\log^2 n)$ ，单点查询 $O(\log n)$ 。它常用作斜率优化的替代，尤其当斜率与查询点都不单调时。

区间最值操作 & 区间历史最值

吉司机线段树（Segment Tree Beats）支持区间取 $\min$ / 取 $\max$ 、区间历史最值等「非简单」区间操作。每个节点维护区间最大值、严格次大值与最大值的个数：区间对 $v$ 取 $\min$ 时，若 $v$ 落在次大值与最大值之间，只需更新最大值这一档，否则递归处理。均摊复杂度为 $O(n\log^2 n)$ 。