2023.7.28 学习笔记

常规
1

ST表

  • 即用f[i][j]表示从i开始向后$2^j-1$个的范围
  • 应用倍增的思想，显然任意一段长度不小于2的st表对应区间都能由左右两段得到

f[i][j] = max ( f[i][j - 1] , f[i + 2^{j-1}][j - 1] )

  • 注意要做到超出数组长度的部分不会对答案造成影响，且不会越界
  • 1.在递推是对右半区间特判
  • 2.扩展数组至原数组3-4倍大，并填充不会造成影响的值
  • 递归更新顺序为先枚举j，再枚举i，且边界为f[i][0]，即长度为1的区间
  • 对于区间最大值查询[l,r],令t = \lfloor log_2(r-l+1) \rfloor
  • 则$ans$ = max(f[l][t] , f[r-2^t+1][t])
void pre()
{
	for(int j = 1;j <= 30;j++)
	{
		for(int i = 1;i + (1 << j) -1 <= N;j++)
		{
			f[i][j] = max(f[i][j] , f[i + (1 << (j - 1))][j - 1])
		}
	}
}
int log2[MAX];
for(int i = 2;i <= N;i++)
{
	if(i == (1 << (log2[i - 1] + 1)) 
		log2[i] = log2[i - 1] + 1;
	else 
		log2[i] = log2[i - 1];
	//等同于 log2[i] = log2[i/2]+1;
}
cin>> N >> M;
for(int i = 1;i <= N;i++)
{
	cin>>num[i];
	f[i][0]=num[i];
}
pre();
for(int i = 1;i <= M;i++)
{
	int x,y;
	cin >> x >> y;
	int len = log2[y - x + 1];
	cout << max(f[x][len] , f[y - (1 << len) + 1)][len])
}
  • RMQ解决的是静态区间最值查询问题，要求查询的区间始终不变

eg1:降雨量

即求区间max，分类讨论

  • 必假情况 \begin{cases} val[x]>val[y](x/y已知) \\ val[x]<=max(val[z])(x和至少一个z已知) \\ val[y]<=val[z](y和至少一个z已知) \end{cases}

  • 必真情况 val[y] >= val > max(val[z]) (x,y,以及区间内的所有z已知)

  • 剩余为可能

  • 预处理st表，O(1)求区间max

倍增求LCA(最近公共祖先)

  • 常见做法有倍增/树剖/RMQ/tarjan离线

  • 考虑暴力求lca，预处理得到两个点的深度，每次选择深度较大的点向上跳一步直到两点重合，重合的位置即为LCA

  • 但复杂度为O(n)

  • 由于跳过头依然是公共祖先，考虑倍增

  • 令fa[i][j]代表i向上跳$2^j$条边到达的节点

  • 则fa[i][j] = fa[fa[i][j-1]][j-1]

  • dfs一遍求出fa[i][0],然后nlogn预处理出所有fa[i][j]，这样向上跳的任意距离都可以被拆分为log段距离之和

  • 查询是的上跳部分分为两段：

  • 第一段跳到深度相同

  • 第二段两点同时上跳到lca

  • 两段路程分别用倍增数组拆分为至多log段完成

代码实现

#include <bits/stdc++.h>
using namespace std;
const int MAX = 500007;
struct edge
{
	int next;
	int to;
} e[MAX << 1];
int eid = 0;
int head[MAX];
int lg[MAX];
int father[MAX][22];
int dep[MAX];
void adde(int x, int y)
{
	e[++eid].to = y;
	e[eid].next = head[x];
	head[x] = eid;
}
void LCA_prework(int u, int lst)
{
	dep[u] = dep[lst] + 1;
	father[u][0] = lst;
	for (int i = 1; (1 << i) <= dep[u]; i++)
	{
		father[u][i] = father[father[u][i - 1]][i - 1];
	}
	for (int i = head[u]; i; i = e[i].next)
	{
		if (e[i].to == lst)
		{
			continue;
		}
		LCA_prework(e[i].to, u);
	}
}
int LCA(int x, int y)
{
	if (dep[x] < dep[y])
	{
		swap(x, y);
	}
	while (dep[x] > dep[y])
	{
		x = father[x][lg[dep[x] - dep[y]] - 1];
	}
	if (x == y)
	{
		return x;
	}
	for (int j = lg[dep[x]] - 1; j >= 0; j--)
	{
		if (father[x][j] != father[y][j])
		{
			x = father[x][j];
			y = father[y][j];
		}
	}
	return father[x][0];
}
int N, M, R;
int read()
{
	int num = 0, bj = 0;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
		{
			bj = 1;
		}
		ch = getchar();
	}
	while (isdigit(ch))
	{
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return bj ? -num : num;
}
int main()
{
	N = read();
	M = read();
	R = read();
	for (int i = 1; i <= N; i++)
	{
		lg[i] = lg[i - 1] + (i == (1 << lg[i - 1]));
	}
	for (int i = 1; i <= N - 1; i++)
	{
		int fr, to;
		fr = read();
		to = read();
		adde(fr, to);
		adde(to, fr);
	}
	LCA_prework(R, 0);
	int x, y;
	for (int i = 1; i <= M; i++)
	{
		x = read();
		y = read();
		printf("%d\n", LCA(x, y));
	}
}

  • 预处理复杂度O(nlogn)，单次查询O(logn)

  • 当要查询超过深度范围的倍增时，可以为根节点构建一个虚拟节点

eg2:货车运输

  • kruskal重构树模板

eg3:求和

  • 树剖/LCA
  • 先考虑k恒定时的做法
  • 预处理每个点到根路径上所有点的深度的k次方和
  • 查询时用类似前缀和的方法提取出路径上的点权值和
  • 令sum为点到根的所有点的深度的k次方和
  • sum+sum[y]-2 * sum[lca(x,y)] + val[lca(x,y)]
  • 发现k的范围极小，对于所有可能的k分别预处理sum即可

eg3:运输计划

  • 二分总耗时t，若有航道的时间大于t，其路径上一定要选择一条修改，使得时间变短，让它小于t
  • 所以改造的点一定在要修改的路径交上，可将每条路径上的每条边的计数+1，最后计数==路径数的即为路径交
  • 用树上查分优化，c+=1,c[y]+=1,c[lca(x,y)]-=2
  • 判断将路径交变成虫洞能否满足所有要求

eg4:仓鼠找sugar

  • 结论题：两条路径相交，等价于存在某一条路径的lca在另一条路径上

1

2

3

3 个赞