夏令营7.26总结

线段树

概念

二叉树

二叉树满足条件：

• 有根树
• 每个节点的孩子不超过两个
• 孩子有左右之分

满二叉树是指所有层都是完整的二叉树，即如果二叉树有$n$层，那么就有$2^n-1$个节点。

完全二叉树是指除了最下一层的节点是从左往右排列且可能不满之外，其他部分是一棵满二叉树。

完全二叉数或满二叉树中，设一个节点的编号为$n$，则其左儿子编号为$2n$，右儿子编号是$2n+1$。

T1 静态RMQ

这题是模板题，所以线段树的模板这里就直接放上来就可以了。

具体的其他内容就不详细写了。

结构体定义部分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e5+3;

struct node{
	int l,r;
	int val;
	node():l(0),r(0),val(0){}
	node(int l,int r,int val):l(l),r(r),val(val){}
}t[N<<2];//这里开是4n的数组是因为如果使用2n的数组是默认是完全二叉树的前提下，但是线段树虽然除了最底下一层是满二叉树，但是最底下一层并不是按顺序紧密排列的。所以要开4n的空间防止越界。

初始化部分

#define ls (i<<1)
#define rs (i<<1|1)

int a[N];
void build(int l,int r,int i){
	t[i]=node(l,r,0);
	if(l==r){
		t[i].val=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[i].val=min(t[ls].val,t[rs].val);

查询部分

int query(int l,int r,int i,int ql,int qr){
	if(ql<=l&&r<=qr){
		return t[i].val;
	}
	int mid=(l+r)>>1;
	int res=1e9+7;
	if(ql<=mid){
		res=min(res,query(l,mid,ls,ql,qr));
	}
	if(qr>mid){
		res=min(res,query(mid+1,r,rs,ql,qr));
	}
	return res;
}
#undef ls//用完后及时undef，防止用多个算法时define冲突。
#undef rs

主函数与处理查询部分

int n,q;

int main(){
	cin>>n>>q;
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	
	build(0,n-1,1);

	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<query(0,n-1,1,l,r-1)<<endl;
	}

	return 0;
}

T2 单点加区间求和

整体步骤：

1. 线段树（Segment Tree）的构建

• 若当前节点表示的区间长度为1（l=r），则直接存储数组对应位置的值。
• 否则，将区间分为左右两半（mid=(l+r)>>1），递归构建左子树和右子树，当前节点的值为左右子树的和。

2. 单点更新操作（update函数）
   当需要给数组中位置p的元素增加x时：

• 从根节点出发，递归找到对应p的叶子节点。
• 更新叶子节点的值（加上x）。
• 回溯更新所有祖先节点的值（每个祖先节点的值为左右子树的和，因此子节点变化后需重新计算）。

3. 区间查询操作（query函数）
   当需要查询区间[ql,qr]的总和时从根节点出发，判断当前节点的区间与查询区间的关系：

• 若当前节点区间完全在查询区间内，直接返回该节点的值。
• 若当前节点区间与查询区间部分重叠，递归查询左子树和右子树，返回两者的和。
• 若完全不重叠，返回 0。

T3

代码的核心功能是维护一个数组，支持两种操作：

• 区间更新：给数组中某个连续区间内的所有元素同时增加一个值。
• 单点查询：查询数组中指定位置元素的当前值。

由于需要频繁进行区间更新（若用朴素方法，每次更新的时间复杂度为$O(n)$，效率极低），线段树结合懒标记是解决这类问题的高效方案，可将单次操作的时间复杂度优化至$O(logn)$。

懒标记是线段树中用于延迟更新的技术：

• 当需要对某个区间执行更新时，若当前节点的区间完全包含在更新区间内，不立即更新其所有子节点，而是在节点上记录一个 “待更新标记”（tag）。
• 只有当后续操作需要访问该节点的子节点时，才将标记 “下放”（pushdown）到子节点，确保子节点的状态正确。

这种机制避免了不必要的重复更新，显著提高了区间更新的效率。

T4

核心功能是维护一个数组，支持两种操作：

1. 区间线性更新：对指定区间[l,r)内的所有元素执行操作$a[i]=(a[i]\times b+c)%MOD$（先乘$b$，再加$c$，最后取模）。
2. 单点查询：查询数组中指定位置$i$的元素经过所有更新后的当前值（取模后）。

由于需要频繁进行区间线性变换（朴素方法时间复杂度为$O(n)$，效率极低），线段树结合双懒标记是最优解决方案，可将单次操作时间复杂度优化至$O(\log n)$。
懒标记下放流程：
若节点存在有效的变换（mul!=1或add!=0），则将变换下放至左右子节点：

• 左子节点：mul=(mul*父节点mul)%MOD，add=(add*父节点mul+父节点add)%MOD。
• 右子节点：同上。
• 清空当前节点的标记（mul=1，add=0），避免重复下放。

T5

代码需要处理两种核心操作：

• 区间线性更新：对数组中$[l,r]$区间内的所有元素执行变换$x\rightarrow(x\times b+c)%MOD$（先乘$b$，再加$c$，最后取模）。
• 区间求和查询：计算数组中$[l,r]$区间内所有元素的和，结果对MOD取模。

由于数组规模可能很大（$n$达$5\times10^5$），且操作频繁（$q$达$5\times10^5$），必须使用高效的数据结构。线段树结合双懒标记能将单次操作的时间复杂度降至$O(\log n)$，满足需求。

T6

核心思路：函数复合线段树

1. 函数复合的特性
   线性函数的复合满足结合律，但不满足交换律，即$(f∘g)∘h=f∘(g∘h)$，但$f∘g≠g∘f$（通常）。因此，区间[l, r)的复合函数需按顺序从左到右复合（$f_l∘f_{l+1}∘…∘f_{r-1}$）。

线段树的每个节点存储对应区间的复合函数，通过子节点的复合函数计算得到。

2. 线段树的结构

每个节点$seg[i]$存储一个线性函数$func(a,b)$，表示该节点对应区间的所有函数复合后的结果。

叶子节点：对应单个线性函数（区间长度为 1）。

非叶子节点：其函数为左子树函数与右子树函数的复合（注意顺序：右子树函数先作用，左子树函数后作用，即$seg[i]=seg[右子树]\times seg[左子树]）$。

T7

核心思路：带区间替换标记的函数复合线段树

1. 函数复合的特性

线性函数的复合满足结合律，因此区间[l,r)的复合函数可通过子区间的复合函数递归计算。

若区间内所有函数均为同一个函数$f$，则复合结果为$f^k$，其中$k$为区间长度。例如，$f^2(x)=f(f(x))$，$f^3(x) = f(f(f(x)))$，可通过快速幂高效计算。

2. 线段树与区间替换标记

每个节点存储：

区间[l, r)的复合函数$f$。

区间替换标记same（true表示区间内所有函数均为tag）。

替换函数tag（当same为true时有效）。

当需要替换区间[l, r)为函数$g$时，若节点区间完全包含在[l, r)内，只需标记same=true并记录tag=g，同时通过快速幂计算节点的复合函数$f=g^k$（$k$为区间长度）。

当需要访问子节点时，需将替换标记下放（pushdown），确保子节点的状态正确。