首页 > 其他分享 >点分治&&点分树

点分治&&点分树

时间：2025-01-15 20:00:23浏览次数：1  
标签：int text 分治 fa 点分树 && siz dis

点分治

前置芝士：树的重心

树的重心指对于一棵无根树上的一点，其分割开的若干子树大小的最大值最小。

一般用 DFS 求解树的重心。初始时，\(\mathit{mxs}=\mathit{sum}=n\)，即树的节点个数。最终的 \(\mathit{rt}\) 即为重心。

void getrt(int u,int fno){
	int s=0;
	siz[u]=1;
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno||del[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		s=max(s,siz[v]);
	}
	s=max(s,sm-siz[u]);
	if(s<mxs) mxs=s,rt=u;
}

点分治

点分治，又名淀粉质，是在树上进行静态统计的算法。这里的静态统计一般是树剖维护不了的，所以我们需要点分治。但在实际应用中，树剖确实能解决很多点分治的题，码量还更小。

点分治的思想是将一棵树拆成许多棵子树进行处理。比如，对于一条路径，可以将其分成两类：经过根节点和不经过根节点的路径。对于前者，可以预处理出每个点到根的路径，然后 \(\text{dis}(u,v)=\text{dis}(u,\mathit{rt})+\text{dis}(v,\mathit{rt})\)，并排除不合法的情况（\(u,v\) 在同一子树中）；对于后者，通过分治转化为前者。

如果是均衡的树，查询一次是 \(O(n\log n)\) 的；如果是一条链，查询将退化为 \(O(n^2)\)。所以分治前对每棵子树找到树的重心做根即可。

P3806 【模板】点分治 1

题意：给定一棵 \(n\) 个点的树，每次询问树上距离为 \(k\) 的点对是否存在。

点分治板子题，分四步走：

  1. 找出树的重心做根，getrt()；
  2. 求出子树各点到根的距离，getdis()；
  3. 统计当前子树答案，calc()；
  4. 分治各个子树，重复上述操作，divide()。
// 核心代码
void getrt(int u,int fno){
	siz[u]=1;
	int s=0;
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno||del[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		s=max(s,siz[v]);
	}
	s=max(s,sum-siz[u]);
	if(s<mxs) mxs=s,rt=u;
}
void getdis(int u,int fno){
	dis[++cnt]=d[u];
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno||del[v]) continue;
		d[v]=d[u]+e[i].w;
		getdis(v,u);
	}
}
void calc(int u){
	judge[0]=1;
	int p=0;
	for(int i=head[u],v;i;i=e[i].to){
		if(del[v=e[i].v]) continue;
		cnt=0;
		d[v]=e[i].w;
		getdis(v,u);
		for(int j=1;j<=cnt;++j)
			for(int k=1;k<=m;++k)
				if(ask[k]>=dis[j])
					ans[k]|=judge[ask[k]-dis[j]];
		for(int j=1;j<=cnt;++j)
			if(dis[j]<MAXK) judge[q[++p]=dis[j]]=1;
	}
	for(int i=1;i<=p;++i) judge[q[i]]=0;
}
void divide(int u){
    del[u]=1;
	calc(u);
	for(int i=head[u],v;i;i=e[i].to){
		if(del[v=e[i].v]) continue;
		mxs=sum=siz[v];
		getrt(v,0);
		divide(rt);
	}
}

稍微解释一下 calc() 函数：前面提到计算经过根节点的路径时需要注意排除不合法情况，所以我们用 \(\mathit{judge}\) 数组存储之前子树中出现过的距离，对于一个子树枚举所有出现过的距离和询问，如果询问距离 \(\text{ask}(k)\) 与 \(\text{dis}(j)\) 的差存在，则此询问合法。

P4178 Tree

题意：给定一棵 \(n\) 个节点的树，边有边权，求树上距离小于等于 \(k\) 的点对数量。

仍然点分治四步走。和板题不一样的地方在于边有边权，以及统计的是数量而不是是否存在。观察到既然是小于等于，可以想到树状数组维护前缀和。于是把所有出现过的距离扔进树状数组里，查询的时候查询前缀和即可。需要注意的是，最后不能忘了统计以根节点为端点的路径。

// 这是我以前的码风
void calc(int u) {
	queue<int> q;
	for (auto vv : g[u]) {
		int v = vv.first, w = vv.second;
		if (del[v]) continue;
		d[v] = w;
		cnt = 0;
		getdis(v, u);
		for (int j = 1; j <= cnt; ++j) {
			if (dis[j] > K) continue;
			ans += ask(K - dis[j]);
		}
		for (int j = 1; j <= cnt; ++j) {
			if (dis[j] > K) continue;
			q.emplace(dis[j]);
			++judge[dis[j]];
			mdf(dis[j], 1);
		}
	}
	while (!q.empty()) {
		if (q.front() <= K) ans += judge[q.front()];
		mdf(q.front(), -judge[q.front()]);
		judge[q.front()] = 0;
		q.pop();
	}
}

P3085 [USACO13OPEN] Yin and Yang G

其实它更广为人知的名字是采药人的路径。

题意：给出一棵 \(n\) 个点的树，每条边为黑色或白色。问满足以下条件的路径条数：路径上存在一个不是端点的点，使得两端点到该点的路径上两种颜色的边数都相等。

首先容易想到的是把边权变为 \(1\) 和 \(-1\)，这样路径边权和为 \(0\) 的路径就是黑白边数相等的路径。

设一个点 \(i\) 到根的距离为 \(\text{dis}(i)\)，则对于一条路径的端点 \(x,y\)，若 \(\text{dis}(x)=-\text{dis}(y)\) 即为平衡。与此同时，若路径上存在一点 \(z\) 使得 \(\text{dis}(z)=\text{dis}(x)\lor\text{dis}(z)=\text{dis}(y)\)，这条路径就符合要求。

我们定义 \(z\) 为路径的 “中转点”。

对于答案的求解是本题的难点，设：

  • \(f_{i,0/1}\) 表示对于当前根，现在正在遍历，距离根的距离为 \(i\)，找不到/找得到中转点的点的个数；
  • \(g_{i,0/1}\) 表示对于当前根，以前遍历过，距离根的距离为 \(i\)，找不到/找得到中转点的点的个数。

\(g\) 的转移是容易的，把当前子树的 \(f\) 复制下来即可。

对于 \(f\) 的计算，我们在 DFS 的过程中开一个桶计算一个距离有没有出现过。如果当前点到根的距离出现过，则证明当前点有一个祖先和当前点的 \(\text{dis}\) 值是相同的，说明这个祖先就是前文说过的 \(z\) 点，即当前点能找到中转点；反之则不能。一遍 DFS 就可以计算 \(f\)。

然后考虑用 \(f\) 和 \(g\) 计算答案。先看计算答案的代码：

ans+=f[N][0]*(g[N][0]-1);
for(int j=-mxd;j<=mxd;++j)
    ans+=f[N+j][1]*g[N-j][1]+f[N+j][1]*g[N-j][0]+f[N+j][0]*g[N-j][1];

首先计算根是中转点的情况，此时找不到中转点的点也可以配对，同时根是端点的情况多算一遍要减去。

对于一组距离为相反数的点对，能否配对取决于这对点中的任意一个能否找到中转点。

剩下的就不是难点了。

AC Code

P3714 [BJOI2017] 树的难题

对于一个点为根，我们可以很容易计算出 \(\text{dep}(i)\) 表示深度，\(\text{sum}(i)\) 表示根节点到 \(i\) 的路径权值。对于任意两点 \(x,y\) 的路径权值就是 \(\text{sum}(x)+\text{sum}(y)-\text{接头的边权相同时的边权}\)。但是判断接头边权相同比较棘手，所以我们创新性地将根节点的所有子树按照接头边权排序。之后就是套路，设 \(f_i\) 表示当前颜色中距离根节点为 \(i\) 的节点数，\(g_i\) 表示以前的颜色中距离根节点为 \(i\) 的节点数。在两个数组中查询 \((\forall y\in\text{son}_u)~\big[l-\text{dep}(y),r-\text{dep}(y)\big]\) 的最大值。记为 \(a,b\)，则用 \(a-c_y+\text{sum}(y)\) 和 \(b+\text{sum}(y)\) 更新答案。

\(f\) 和 \(g\) 的转移都是容易的，但因为涉及到查询区间最大值，所以改成线段树。

AC Code

点分树（动态点分治）

点分树和点分治的关系仅仅在于建树时运用了点分治的思想。又因其主要解决带修问题，故又名动态点分治。

点分树

定义：利用点分治，以每个子树的重心做根，重构出来的一棵树。

实话说，点分树和原树的形态没有任何关系。有什么用？主要是两个性质：

  1. 树高严格小于等于 \(\log n\)！
  2. 原树两点 LCA 在点分树两点的路径上！

第一条性质最为重要，它可以让我们做出很多不可思议的事情。

比如，在点分树上做 \(n\) 遍暴力跳父亲，最终时间复杂度却是 \(O(n\log n)\)。

比如，对点分树的每一个节点开一个 vector 存储子树所有节点的信息，空间复杂度却同样是 \(O(n\log n)\)。

有的问题我们并不是特别关注树的形态特点，比如路径问题、连通块问题、关键点问题等，以路径问题为例，我们并不一定要算出两点的 LCA 才能计算距离，我们只需找到路径上的一个分割点即可。

点分树题的一般解题技巧是开两个数据结构（可以是数组、vector、线段树等），分别维护对 \(\boldsymbol u\) 的贡献和对 \(\boldsymbol u\) 的父亲的贡献。分别记为 \(f_u\) 和 \(g_u\)，因为点分树可以暴力跳父亲，所以我们在从 \(u\) 跳到 \(\text{fa}(u)\) 时，需要加上多出来的 \(f_{\text{fa}(u)}\)，同时减去重复算的 \(g_u\)。

点分树的常数巨大，写点分树必须注意常数问题。

P6329 【模板】点分树 | 震波

题意：给定一棵 \(n\) 个点的树，点有点权。每次查询距离点 \(x\) 不超过 \(k\) 的点的点权和。带修，强制在线。

建出点分树，记 \(u\) 在点分树上的父亲为 \(\text{fa}(u)\)，\(u,v\) 两点在原树上的距离为 \(\text{dis}(u,v)\)。

第一步是用倍增/树剖/ST 表求出树上两点间距离。建议使用树剖，因为码量小还跑得快（跑不满的 \(\log n\)）。不建议使用倍增是因为复杂度是实打实的 \(\log n\)，会给整体复杂度多套一个 \(\log\) 导致复杂度错误。不建议使用 ST 表是因为懂的都懂。

第二步，开两棵动态开点线段树，设 \(\text{sg}(x,a,b)\) 表示在点分树上以 \(x\) 为根的子树中到 \(x\) 的原始距离在 \([a,b]\) 之间的权值和，\(\text{ch}(x,a,b)\) 表示在点分树上以 \(x\) 为根的子树中到 \(\text{fa}(x)\) 原始距离为 \([a,b]\) 之间的权值和。

查询时，暴力跳父亲，当查询距离节点 \(x\) 不超过 \(k\) 的节点的权值和时，先将答案加上 \(\text{sg}(x,0,k)\)，再跳 \(x\) 在点分树上的所有祖先 \(u\)，答案先加上 \(\text{sg}\big(\text{fa}(u),0,k-\text{dis}(x,\text{fa}(u))\big)\)，再减去 \(\text{ch}\big(u,0,k-\text{dis}(x,\text{fa}(u))\big)\)。减去是为了容斥掉多算的答案，手摸一下就能理解。这也是点分树的基本操作。

修改时，暴力跳父亲修改即可。

struct{
    ... // 树剖求LCA和树上两点距离，不再展示
}L;
struct{
    // 单加区查的动态开点线段树
	#define lp st[p].lc
	#define rp st[p].rc
	int rt[MAXN],tot;
	struct SegTree{
		int lc,rc,c;
	}st[MAXN<<5]; // 空间复杂度由数据规模决定
	void chg(int x,int k,int s,int t,int&p){
		if(!p) p=++tot;
		if(s==t) return st[p].c+=k,void();
		int mid=(s+t)>>1;
		if(x<=mid) chg(x,k,s,mid,lp);
		else chg(x,k,mid+1,t,rp);
		st[p].c=st[lp].c+st[rp].c;
	}
	int query(int l,int r,int s,int t,int p){
		if(!p) return 0;
		if(l<=s&&t<=r) return st[p].c;
		int mid=(s+t)>>1,res=0;
		if(l<=mid) res+=query(l,r,s,mid,lp);
		if(mid<r) res+=query(l,r,mid+1,t,rp);
		return res;
	}
    // 建树略有不同，wc是根，d是距离
    // 相当于给线段树上距离根节点d的位置加上了点权w[u]
	void build(int u,int fno,int wc,int d){
		chg(d,w[u],0,n,rt[wc]);
		for(int i=head[u];i;i=e[i].to)
			if(e[i].v^fno&&!del[e[i].v])
				build(e[i].v,u,wc,d+1);
	}
}sg,ch;
struct{
	int sum,mxs,rt,siz[MAXN];
	int dis[MAXN][21],dep[MAXN],fa[MAXN];
	void getrt(int u,int fno){
		siz[u]=1;
		int s=0;
		for(int i=head[u],v;i;i=e[i].to){
			if((v=e[i].v)==fno||del[v]) continue;
			getrt(v,u);
			siz[u]+=siz[v];
			s=max(s,siz[v]);
		}
		s=max(s,sum-siz[u]);
		if(s<mxs) mxs=s,rt=u;
	}
	void build(int u){
		del[u]=1;
        // sg建树时根节点是u，维护的信息是到u的信息
		sg.build(u,0,u,0);
		for(int i=head[u],v;i;i=e[i].to){
			if(del[v=e[i].v]) continue;
			sum=mxs=siz[v];
			getrt(v,0);
            // ch建树时根节点是子树重心，但维护的距离是到根节点父亲的距离
			ch.build(v,0,rt,1);
			fa[rt]=u;
			dep[rt]=dep[u]+1;
			build(rt);
		}
	}
	void init(){
        // 找重心
		sum=mxs=n;
		getrt(1,0);
		build(rt);
        // 树剖预处理
		L.dfs(1,0);
		L.dfs2(1,1);
        // 预处理dis，dis[i][j]表示点分树上i的j级祖先在原树上的距离
		for(int i=1;i<=n;++i)
			for(int j=i;j;j=fa[j])
				dis[i][dep[i]-dep[j]]=L.getdis(i,j);
	}
	int query(int x,int y){
		int res=sg.query(0,y,0,n,sg.rt[x]);
		for(int i=x,d;fa[i];i=fa[i]){
			d=dis[x][dep[x]-dep[fa[i]]];
			res+=sg.query(0,y-d,0,n,sg.rt[fa[i]]);
			res-=ch.query(0,y-d,0,n,ch.rt[i]);
		}
		return res;
	}
	void chg(int x,int y){
        // 之所以y-w[x]是因为题目中是“修改为”，此时加上差值就等于修改为
		sg.chg(0,y-w[x],0,n,sg.rt[x]);
		for(int i=x,d;fa[i];i=fa[i]){
			d=dis[x][dep[x]-dep[fa[i]]];
			sg.chg(d,y-w[x],0,n,sg.rt[fa[i]]);
			ch.chg(d,y-w[x],0,n,ch.rt[i]);
		}
	}
}P;

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) w[i]=read();
	for(int i=1,u,v;i<n;++i){
		u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	P.init();
	int lst=0;
	while(m--){
		int op=read(),x=read(),y=read();
		x^=lst,y^=lst;
		if(!op) write(lst=P.query(x,y));
		else P.chg(x,y),w[x]=y;
	}
	return fw,0;
}

P3345 [ZJOI2015] 幻想乡战略游戏

题意：动态求一棵树的带点权、边权重心。

本题考察对点分树的理解。观察到如果当前点不是带权重心，那么一定有一个儿子会比它更优，查询时不断像这样跳儿子就行。又看到查询是动态的，于是考虑点分树。建好点分树之后我们可以暴力算出每一个点作为根时的答案，把儿子的答案和当前点的答案作比较，如果有儿子更优就往儿子跳即可。

于是问题转化为已知一个点求树上所有点到这个点的带权距离。具体实现就是套路了：设 \(\text{sum}(i)\) 表示点分树上 \(i\) 点子树的点权和，\(\text{smd}(i)\) 表示 \(i\) 点子树所有点到 \(i\) 的距离和，\(\text{smf}(i)\) 表示 \(i\) 点子树所有点到 \(\text{fa}(i)\) 的距离和。同样，修改时暴力跳父亲，查询时容斥查询即可。

ll sum[MAXN],smd[MAXN],smf[MAXN];
void getrt(int u,int fno){
	siz[u]=1;
	int s=0;
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno||del[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		s=max(s,siz[v]);
	}
	s=max(s,sm-siz[u]);
	if(s<mxs) mxs=s,rt=u;
}
void build(int u){
	del[u]=1;
	for(int i=head[u],v;i;i=e[i].to){
		if(del[v=e[i].v]) continue;
		mxs=sm=siz[v];
		getrt(v,u);
		fa[rt]=u;
		g[u].emplace_back(v,rt);
		build(rt);
	}
}
void mdf(int u,ll k){
	sum[u]+=k;
	for(int i=u;fa[i];i=fa[i]){
		ll ds=L.getdis(u,fa[i]);
		sum[fa[i]]+=k;
		smd[fa[i]]+=k*ds;
		smf[i]+=k*ds;
	}
}
ll count(int u){
	ll res=smd[u];
	for(int i=u;fa[i];i=fa[i]){
		ll ds=L.getdis(u,fa[i]);
		res+=(sum[fa[i]]-sum[i])*ds;
		res+=smd[fa[i]]-smf[i];
	}
	return res;
}
ll query(int u){
	ll x=count(u);
	for(auto vv:g[u])
		if(count(vv.first)<x)
			return query(vv.second);
	return x;
}

int main(){
	n=read(),Q=read();
	for(int i=1,u,v,w;i<n;++i){
		u=read(),v=read(),w=read();
		addedge(u,v,w),addedge(v,u,w);
	}
	mxs=sm=n;
	getrt(1,0);
	int RT=rt;
	build(rt);
	L.dfs(1,0);
	L.dfs2(1,1);
	while(Q--){
		int x=read(),y=read();
		mdf(x,y);
		write(query(RT));
	}
	return fw,0;
}

P3241 [HNOI2015] 开店

先考虑如果没有 \(L,R\) 的限制怎么做。不用考虑，就是上一道题。

那么加上 \(L,R\) 的限制呢？

其实这个扩展是很巧妙的，利用了点分树的第二条性质。我们把原来的 \(\text{smd}\) 和 \(\text{smf}\) 改成 vector 数组，把原来的 += 改成 emplace_back 一个点的点权信息和贡献信息。这样处理完毕之后，把每个点的 vector 按照点权排序，再把第二维前缀和一下，于是查询的时候只需用 \(\texttt{lower_bound}\) 和 \(\texttt{upper_bound}\) 锁定区间 \([L,R]\)，前缀和一减就是答案。至于 \(\text{sum}\)，我们可以在查询出 \(L-1\) 和 \(R\) 之后同样一减就是答案。最后统计答案就是老套路了。

这题有坑。

int mxs,sm,rt,siz[MAXN];
bool del[MAXN];
void getrt(int u,int fno){
	int s=0;
	siz[u]=1;
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno||del[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		s=max(s,siz[v]);
	}
	s=max(s,sm-siz[u]);
	if(s<mxs) mxs=s,rt=u;
}
struct PIL{
	int first;
	ll second;
	PIL(int u,int v):first(u),second(v){}
	bool operator<(const PIL&x)const{
		return first<x.first;
	}
};
vector<PIL>smd[MAXN],smf[MAXN];
int fa[MAXN];
void dfs(int u,int fno,ll w){
	smd[rt].emplace_back(x[u],w);
	if(fa[rt]) smf[rt].emplace_back(x[u],L.getdis(u,fa[rt]));
	for(int i=head[u],v;i;i=e[i].to){
		if(del[v=e[i].v]||v==fno) continue;
		dfs(v,u,w+e[i].w);
	}
}
void build(int u){
	del[u]=1;
	dfs(u,0,0);
	for(int i=head[u],v;i;i=e[i].to){
		if(del[v=e[i].v]) continue;
		mxs=sm=siz[v];
		getrt(v,0);
		getrt(rt,0);
		fa[rt]=u;
		build(rt);
	}
}
ll query(int opt,int u,int l,int r,int&sz){
	int L,R;
	if(!opt){
		L=lower_bound(smd[u].begin(),smd[u].end(),PIL(l,0ll))-smd[u].begin()-1;
		R=upper_bound(smd[u].begin(),smd[u].end(),PIL(r,0ll))-smd[u].begin()-1;
	}else{
		L=lower_bound(smf[u].begin(),smf[u].end(),PIL(l,0ll))-smf[u].begin()-1;
		R=upper_bound(smf[u].begin(),smf[u].end(),PIL(r,0ll))-smf[u].begin()-1;
	}
    // 这个L实际上是L-1所在位置，R就是R的位置
	sz=R-L;
	ll res=0;
	if(!opt){
		if(R>=0&&R<(int)smd[u].size()) res+=smd[u][R].second;
		if(L>=0&&L<(int)smd[u].size()) res-=smd[u][L].second;
	}else{
		if(R>=0&&R<(int)smf[u].size()) res+=smf[u][R].second;
		if(L>=0&&L<(int)smf[u].size()) res-=smf[u][L].second;
	}
	return res;
}

int main(){
	n=read(),Q=read(),A=read();
	for(int i=1;i<=n;++i) x[i]=read();
	for(int i=1,u,v,w;i<n;++i){
		u=read(),v=read(),w=read();
		addedge(u,v,w),addedge(v,u,w);
	}
	L.dfs(1,0);
	L.dfs2(1,1);
	sm=mxs=n;
	getrt(1,0);
	getrt(rt,0);
	build(rt);
	for(int i=1;i<=n;++i){
		sort(smd[i].begin(),smd[i].end());
		sort(smf[i].begin(),smf[i].end());
		if(smd[i].size()>1)
			for(auto it=next(smd[i].begin());it!=smd[i].end();++it)
				it->second+=prev(it)->second;
		if(smf[i].size()>1)
			for(auto it=next(smf[i].begin());it!=smf[i].end();++it)
				it->second+=prev(it)->second;
	}
	ll lst=0;
	while(Q--){
		int u=read(),l=(read()+lst)%A,r=(read()+lst)%A,sz1,sz2;
		if(l>r) swap(l,r);
		lst=query(0,u,l,r,sz1);
		for(int i=u;fa[i];i=fa[i]){
			lst+=query(0,fa[i],l,r,sz2)-query(1,i,l,r,sz1);
			lst+=(sz2-sz1)*L.getdis(fa[i],u);
		}
		write(lst);
	}
	return fw,0;
}

标签：int,text,分治,fa,点分树,&&,siz,dis
From： https://www.cnblogs.com/laoshan-plus/p/18673651

相关文章

  • 分治的思想
    分治算法是一种很重要的算法策略，它的基本思想是将一个复杂的问题分解成更多相同或相似的子问题，所以分治算法通常以递归的方式实现。就像之前讲的归并排序(不知道可以翻翻之前的博客),将排序的过程不断拆解，排n个数可以排两个n/2个数，看做排n/2再/2，排4段数，最后可以看做排n段长度......
  • 线段树分治-学习笔记
    线段树分治-学习笔记阅前须知：本文给出了线段树分治的一道例题以及多道习题，同时给出了部分实现的代码，帮助学习线段树分治。总述线段树分治是一种离线算法，在于把修改挂在线段树的节点上，通过遍历线段树求出每个叶子节点的答案，以减小复杂度。例题P5787二分图题目大意：\(n\)个点......
  • 点分治
    更新日志2025/01/07：开工。概念点分治，通常用于处理大规模的树上路径信息问题。思路我们将原问题划分为多种，对于每个节点，统计经过这个节点且位于这棵子树内的路径答案。为了缩减复杂度，对于每一棵子树，我们都找到它的重心，以重心为新根在子树内进行操作。找重心示例：intcn......
  • 分治杂记
    分治杂记分治（DivideandConquer），就是把一个复杂的问题分成若干子问题，分别求解。本质是缩小了问题的规模。普通的分治[ABC373G]NoCrossMatching给定平面上的\(n\)个黑点和\(n\)个白点，构造一种方案，将黑白点两两匹配并连线段，使得任意两条线段不相交。\(n\leq100\)，保......
  • 深入了解分治 FFT
    问题提出算法应用于问题，分治FFT的出现是为了解决这样一个问题：给定序列\(g_{1\dotsn-1}\)，求序列\(f_{0\dotsn-1}\)。其中\(f_i=\sum_{j=1}^if_{i-j}g_j\)，边界为\(f_0=1\)。具体可以见【模板】分治FFT-洛谷对于这个问题我们要求做到\(\Theta(n\log^2n)\)的......
  • 【优选算法 & 分治】深入理解分治算法：分治算法入门小专题详解
             快速排序算法   (1)快速排序法       (2) 快排前后指针     (3)快排挖坑法   颜色分类  题目解析    算法原理   算法原理和移动零非常相似  简述移动零的算法原理   ......
  • [学习笔记] 根号分治
    https://www.cnblogs.com/guanlexiangfan/p/15553329.htmlhttps://blog.csdn.net/qq_35684989/article/details/127190872放一下讲得比较好的根号分治。根号分治，一般将数据分为\(a<\sqrtn\)的与\(a>\sqrtn\)的进行分类讨论。一般可以配合预处理将\(O(n^2)\)的做法优化......
  • 分治策略——算法学习（二）
    分治策略——算法学习（二）前言在算法设计的世界中，分治策略（DivideandConquer）是一种极具魅力的思想，它通过将复杂问题拆解为多个规模较小但结构类似的子问题，从而以递归的方式解决问题。这种策略不仅高效而且直观，为许多经典算法的诞生奠定了基础，如快速排序（QuickSort）、归并排序（Merg......
  • 分治总结
    有各种分治：CDQ分治，树上分治，数据结构上分治，根号分治，etc.普通分治求逆序对用归并排序求逆序对。Sol：其实逆序对是在归并排序时顺带求的，主要是归并排序。我们要对区间\([l,r]\)从小到大排序，先对\([l,mid],[mid+1,r]\)排序（这一步体现分治思想）。现在考虑怎么把两边合并。我们定义......
  • 一文详解“分治—归并“在算法中的应用
    找往期文章包括但不限于本期文章中不懂的知识点：个人主页：我要学编程(ಥ_ಥ)-CSDN博客所属专栏： 优选算法专题这里的归并与我们在数据结构中学习的归并排序是一样的，我们可以先来复习一下归并排序。用一道题来帮助我们回想起归并排序的细节。目录912.排序数组LCR170.交易......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99