织梦门户网站做大后,电子商务网站规划设计包括哪些方面,建筑给排水识图教程久久建筑网,网站开发课程概要
#xff08;这是笔者刚学完趁热写的博客 由于也是初学#xff0c;所以可能会对初学读者比较友好吧 毕竟你不明白的地方我可能也迷惑过#xff09;
学完感觉树链剖分的设计真的很巧妙 其主要用途是压缩树上路径 又是一个n到log的优化
原理
先引定义#xff1a;
设…概要
这是笔者刚学完趁热写的博客 由于也是初学所以可能会对初学读者比较友好吧 毕竟你不明白的地方我可能也迷惑过
学完感觉树链剖分的设计真的很巧妙 其主要用途是压缩树上路径 又是一个n到log的优化
原理
先引定义
设定每个结点所有儿子中子树的结点个数最多的儿子为重儿子 重儿子连成的链叫做重链 每条重链深度最小的点叫做重链的链头
能得出一个很重要的结论 从根出发的任意一条路径经过的重链数不超过logmm为边数 这是树链剖分提速的关键 这个结论画个图就能很容易的看出来路径产生断点必然意味着有一条至少比原路径结点更多的子树
应用
树链剖分常常和dfs序结合 如果再dfs时先dfs重儿子重链的dfs序就是连续的 我们就可以一起进行修改 这样就可以用线段树之类的结构进行维护了
实现
那么接下来我们尝试代码实现
dfs
先树上dfs一遍求出每个结点的深度、父亲、子树大小等基本信息 顺便把重儿子也求了
void dfs1(int x,int f){size[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dep[to]dep[x]1;fa[to]x;dfs1(to,x);size[x]size[to];if(!hson[x]||size[to]size[hson[x]]) hson[x]to;}return;
}再dfs一遍求dfs序和链头 注意先dfs重儿子
void dfs2(int x,int tp){top[x]tp;dfs[tot]x;pos[x]tot;a[tot]b[x];if(!hson[x]) return;dfs2(hson[x],tp);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa[x]) continue;if(tohson[x]) continue;else dfs2(to,to);}return;
}dfs数组和pos数组互相映射按需取食
修改查询
dfs之后就要开始干活了 修改和查询其实一个道理 两个点如果链头相同就说明在同一条重链上 直接对两者之间的dfs区间处理即可 否则就选深度大的那个点让它往上跳一条链同时对这条链处理 直到两点在同一条重链上为止 对区间的修改查询当然离不开强大的线段树啦
void roadchange(int x,int y,int v){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);longchange(1,1,tot,pos[top[x]],pos[x],v);xfa[top[x]];}if(dep[x]dep[y]) swap(x,y);longchange(1,1,tot,pos[y],pos[x],v);return;
}
ll roadask(int x,int y){ll ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);anslongquery(1,1,tot,pos[top[x]],pos[x]);
// printf(%d %d\n,pos[top[x]],pos[x]);ans%mod;xfa[top[x]];}if(dep[x]dep[y]) swap(x,y);anslongquery(1,1,tot,pos[y],pos[x]);
// printf(%d %d\n,pos[y],pos[x]);return ans%mod;
}线段树
不知道怎么写就点这里吧
细节
这是笔者第一次写的时候遇到的一些小的问题 与你共勉吧 1.线段树访问时应该是dfs序小的写在前也就是深度小的在前 2.踩一个坑已经足够所以没有2了 thanks for reading
