算法合集之《分治讲义算法在树的路径问题中的应用》

1
IOI目录】
【序言】........................................................................................................................ 3 【正文】........................................................................................................................ 4 一.树的分治算法.................................................................................................... 4 基于点的分治：.............................................................................................. 4 基于边的分治：.............................................................................................. 4 效率分析：...................................................................................................... 5 【例 1】树中点对统计................................................................................... 8 算法分析................................................................................................... 8 【例 2】Free Tour 2 ...................................................................................... 10 算法分析................................................................................................. 10 【本节小结】................................................................................................ 13 二．树的路径剖分算法：................................................................................... 14 【例 3】Query On a Tree.............................................................................. 14 算法分析................................................................................................. 14 引入路径剖分......................................................................................... 14 轻重边路径剖分..................................................................................... 15 【例 4】黑白树 ........................................................................................... 17 算法分析................................................................................................. 17 【小结】........................................................................................................ 18 路径剖分与树的分治的联系：.................................................................... 19 【例 5】Query On a Tree Ⅳ ........................................................................ 20 算法分析................................................................................................. 20 【本节小结】................................................................................................ 23 三．树的分治的进一步探讨：........................................................................... 24 如何改进基于边的分治的时间复杂度........................................................ 24 使用基于边的分治解决【例 2】................................................................. 26 使用基于边的分治解决【例 5】................................................................. 27 四．全文总结....................................................................................................... 28 【参考文献】.............................................................................................................. 29 【感谢】...................................................................................................................... 29 【附录】...................................................................................................................... 29

精选ppt课件
12
合并排序
&最坏时间复杂度：O(nlogn) &平均时间复杂度：O(nlogn) &辅助空间：O(n)
精选ppt课件
13
棋盘覆盖
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格 不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋 盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的 特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不 得重叠覆盖。
chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘
// 覆盖左上角子棋盘
if (dr >= tr + s && dc < tc + s)
iefl/cs(/deh特re{<s/殊/st此rB方+o棋复格as盘r在&杂d中&(此tr度d无,棋ctc特分盘<, d殊t中cT r析,方+d(ck 格s,))s) ; 4T(ke O l/cbs1 /(eho特1 )ae{) r/s殊d/s[用O tB方r o+(格t1 a号s)r在]d[Lt(此c型tk kr++棋骨s s,盘牌t-0 0 c中覆1, ]d盖=r, t右d;c上, s角);
算法总体思想
n 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。
分分治割T法成(n的一) 设些计规模思较想是小=，的相将同一n问个题难，以以直便接各解个决击的破大，问题，
分而治之。
n/2
n/2
n/2
n/2
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4精)T选(np/4p)t课T件(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/54)T(n/4

分治策略的原理
总结词
分治策略的原理是将问题分解为若干个较小的子问题，解决 这些子问题，然后将子问题的解决方案组合起来，形成对整 个问题的解决方案。
详细描述
分治策略的核心是将问题分解为若干个子问题，这些子问题 应该尽可能地简单、独立，并且能够被有效地解决。解决这 些子问题后，将它们的解决方案组合起来，形成对整个问题 的解决方案。
项目管理
在项目管理中，分治策略有助于将一个复杂的项目分解为多个子项目，分别进行管理和推 进，提高项目的管理效率。
决策分析
在决策分析中，分治策略有助于将一个复杂的问题分解为多个子问题，分别进行评估和决 策，提高决策的科学性和准确性。
问题解决
在日常生活中，分治策略有助于将一个复杂的问题分解为多个小问题，逐一解决，最终找 到问题的解决方案。例如，在解决家庭纠纷、组织活动等场景中都可以运用分治策略。
THANKS。
高解决问题的速度。
简化问题
将复杂问题分解为更小、更易 于处理的部分，有助于理解和
解决每个子问题。
资源优化
分治策略可以更有效地分配资 源，例如计算资源和人力资源 ，从而提高资源利用效率。
提高准确性
通过分别解决子问题，可以减 少全局解决方案中的错误和误
差。
分治策略的缺点
数据传输成本
合并子问题的复杂性
在解决分治问题时，子问题之间可能需要 进行大量数据传输和通信，这可能导致额 外的计算和通信开销。
问题的目的。
组合数学
在组合数学中，分治策略常用于 解决一些与排列、组合、概率等 相关的问题。通过将问题分解为 多个子问题，简化问题的难度，
从而找到解决方案。
几何学
在几何学中，分治策略常用于解 决一些与面积、体积、最值等相 关的问题。通过将大问题分解为 小问题，逐一解决，最终找到问

R
MaxR Max{D(i) Dist(i, R)} L
R
Opt = 与此链的重合部分在[L,R]的路径的最大长度
Query On a Tree Ⅳ
设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左 右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如 下转移：
MaxL(P) Max{MaxL(Lc), Dist(L, Mid 1) MaxL(Rc)}
2.为了改进基于边的分治的最坏复杂度，我们 将一个结点个数为N的树改造成了一个结点个数为2N 的新树，自然增加了常数。
算法的常数
基于链的分治 基于点的分治 基于边的分治 未改进的 基于边的分治
N=100000 1.17s M=100000
1.78s
2.28s
2.13s
N=100000 2.35s M=500000
设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左
右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如
下转移：
Opt(Lc), Opt(Rc),
Opt(P) Max{
}
MaxR(Lc) MaxL(Rc) Dist (Mid, Mid 1)
Opt
L
R
Opt
L
L
Opt
R
R
Query On a Tree Ⅳ
树的路径问题 以路径为询问对象的题目
POJ1741,树中点对统计 SPOJ QTREE,FTOUR2,QTREE4 Astar2008复赛 黑白树
论文内容
一、树的分治算法 树的分治的两种常见形式：
二、基树于的点路的径分 剖治分算法 三、基树归于的纳边分为的治基分 算 于治法链的的进分一治步探讨