分治思想小结

各种关于分治方法的大合集,只是为了怕自己忘记,实际上都是一些很傻逼的东西。。。

分治的主要思想

把一个大小为nn的问题划分成kk部分(往往k=2k=2),通常每一部分大小为nk\frac{n}{k}

递归解决每一部分,然后合并每一部分的答案,并计算原问题的答案,我们假设这一步复杂度为A(n)A(n)

有总复杂度,可以用主定理计算

一些简单的复杂度计算:

  • A(n)=O(n)A(n) = O(n),那么T(n)=O(nlogn)T(n)=O(n\log n)
  • A(n)=O(n1+ϵ)A(n) = O(n^{1 + \epsilon}),那么T(n)=A(n)T(n) = A(n)

一个优化的小技巧

当分治区间小于某个值(如20)时,直接跑暴力

这对于某些常数较大的分治而言很有用(比如FFT等)

点分治

题型

往往是统计树上路径条数的问题

实现过程

  • 找重心
  • 统计过重心的答案
  • 分治递归计算

复杂度

因为每次找的重心,分下去规模至少除以2,保证了递归层数不超过O(logn)O(\log n)。计算答案是O(n)O(n)的,所以总复杂度是O(nlogn)O(n\log n)的。如果统计答案的时候还要用数据结构维护的话就往复杂度上套log\log

网格图上的分治

Problem

给一个nmn*m的带权网格图,每次询问两点之间最短路

Solution

首先有一个比较暴力的分治方法

每次找到网格图的中线,把网格图划分成左右两部分。

处理出中线上的所有点到每个点的最短路,复杂度是O(n2mlog(nm))O\big(n^2m\log (nm)\big)

考虑询问的每一对点:

  • 如果分别位于中线两侧,那么显然最优方案一定经过中线,计算此时答案并停止这个询问往下递归
  • 如果位于中线同一侧,计算经过中线时对答案的贡献,并且这个询问还需要往下递归

这样做的话每个询问最多会被计算答案O(log(n))O(\log(n))次,所以是对的

总复杂度T(n,m)=T(n2,m)+O(n2log(nm))T(n,m) = T(\frac{n}{2}, m)+O(n^2\log (nm))

nn比较大的时候复杂度会爆炸

考虑优化,每次都分割较大的那一维,复杂度可以做到O((nm)1.5)O((nm)^{1.5})

显然这个也能做到在线

CDQ分治

用来解决三维偏序问题(再高维可以直接套,当然维度再高就没有什么意义了。。。)

Description

nn个点,每个点有三个属性a,b,ca,b,c,对于每个ii求满足ajai,bj<bi,cjcia_j\le a_i, b_j\le <b_i, c_j\le c_ijj个数

Solution

先排序去掉第一维的限制

接着考虑分治,每次分成左半段和右半段,考虑跨区间的贡献

因为第一维已经排好序,所以此时所有右半段的点不会对左半段产生贡献

左右两侧分别按第二维排序,用BIT统计第三维限制下的答案

整体二分

先考虑这样一个问题:长度为nn的数列,求[l,r][l,r]中第kk大的数

这个显然是可以二分答案做的,每次对于二分出的一个答案,统计区间内比它小的数的个数来check

那么如果有mm个这样的询问呢?

顾名思义,整体二分就是把这样很多的二分答案放到一起来处理

相当于是在值域上分治,把操作和值域丢一起算答案

递归函数f(l,r,L,R)f(l, r, L, R)表示当前二分答案区间为[l,r][l, r],答案可能在这个区间内的修改/询问的编号在[L,R][L, R]

每次将答案二分,把[L,R][L,R]里的修改操作按被修改数的权值mid\le mid>mid>mid分成左右两边,如果mid\le mid,就把它下标所在位置在BIT里+1。

[L,R][L,R]里的查询操作按BIT上查询区间里的sumksum\ge k<k<k分成左右两边,如果k\ge k就丢左边,否则那么kk减去sumsum,丢右边。不断分治即可

分治优化Dp

长得像这样的dp:dp[i]=minj<idp[j]+w(j,i)dp[i] = \min_{j < i}dp[j] + w(j, i)

还是把序列分成两半,先在左半边上整体做dp,然后计算所有跨区间的贡献(也就是左半部分dp值对右半部分的贡献),然后对右半边做dp

具体这类题目,往往和斜率优化dp比较像。需要对于左半边区间维护一个凸包,右半边在上面查询即可

分治FFT

见这里

感谢你的赞赏!