Chlience

【算法】分治 & CDQ分治 小结
1 分治1.1 基本思想分治,分而治之,就是把一个复杂的问题分成两个或更多的相同/相似的子问题,直到子问题可以简单...
扫描右侧二维码阅读全文
15
2018/10

【算法】分治 & CDQ分治 小结

1 分治

1.1 基本思想

分治,分而治之,就是把一个复杂的问题分成两个或更多的相同/相似的子问题,直到子问题可以简单的直接求解,原问题的解即为子问题的解的合并

$$T(n) = aT(\frac n b) + f(n)$$

其中 $T(n)$ 表示一个规模为 $n$ 的问题运行时间,共分为 $a$ 个规模为 $\frac n b$ 个子问题,将子问题 分+并 的时间为 $f(n)$

渐进时间复杂度请自行分析

1.2 一般步骤

每一层递归上都有三个步骤:

  1. 分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题
  2. 解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题
  3. 合并:将各子问题的解合并为原问题的解

1.3 能用分治法解决问题的特征

  1. 原问题能划分为几个形式相同的规模较小的子问题
  2. 子问题的解能合并为原问题的解
  3. 子问题之间相互独立

$1,2$ 两点是能否使用分治的关键,而 $3$ 则保证了分治的效率

1.4 经典问题

下面给出几个经典分治问题

  1. 归并排序(逆序对)
  2. 快速幂(有点奇怪)

2 CDQ分治

2.1 基本思想

  1. 划分为两部分
  2. 递归前半部分
  3. 计算前半部分对后半部分的贡献
  4. 递归后半部分

本质上使用的是归并排序的思想,以方便计算某个贡献,并维护序列

2.2 和普通分治的区别

普通分治 中,每一个子问题只解决它本身
CDQ分治 中对于划分出来的两个部分,前一个部分影响后一个部分

2.3 适用的情况

显然,既然要计算前半部分对后半部分的贡献,那么需要有单调性
一般可以用 时间/空间等进行划分
一般来说划分后的两个操作序列通过 归并排序 计算出前半部分对后半部分的贡献,这样就将其变成了一个静态问题(时间/空间),这样我们就解决了一维的限制,也就是 降维
【算法】按时间分治的一类算法 中也有所提及

一般来说,通过降维,就可以顶一层数据结构,不用写树套树啦!

2.4 经典问题

三维偏序
BZOJ 3262 陌上花开 题解

BZOJ 2716 [Violet 3]天使玩偶 [未完成]()

四维偏序
HDU 5126 stars [未完成]()

也就是传说中的 CDQ 套 CDQ ε=ε=ε=┏(゜ロ゜;)┛
当然 K-D tree 好像也行

高维偏序
不在本篇文章讨论范围内

但是你要记住:十维以上 不如n方 暴力进队 乱搞AC

END

Last modification:October 16th, 2018 at 09:00 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment