拆散sqrt与log的恋爱关系——关于复杂度平衡

引言

当诗乃酱在做毒瘤DS题的时候总会YY出这样的复杂度:

O(nsqrtnlogn)

众所周知,根号科技本身就是一种骗分技巧,在根号上加个log还想草过那你在想P吃(人形自走小常数制造机和欧气神请忽略这句话)

1、基础平衡

即通过调整分块/莫队/根号分治的块大小来平衡复杂度。

典型例子:带修改莫队。

具体实践:

问题:求区间[l,r]中小于等于x的数的个数

可以随意YY出一个整块块内二分散块暴力统计的算法。设块大小为B,可以发现整块二分复杂度为O(n^2logn/B),散块复杂度为O(nB)。使复杂度平衡,不难列出等式n^2logn/B=nB可解得当B=sqrt(nlogn)时可使两个复杂度达到平衡。

2、log与根号的平衡

以下方法对于修改复杂度与查询复杂度不平衡有效。

例如有算法修改O(logn)查询O(sqrtnlogn),那么我们可以考虑将其平衡为O(sqrtn)修改O(sqrtn)查询。

考虑log的来历:

1、来自另一个数据结构。此时我们考虑以分块代替此数据结构。

以树状数组为例。树状数组可以实现的功能:O(logn)单点修改O(logn)查询前缀和。

事实上我们可以把这两个复杂度平衡到一边。

O(sqrtn)单点修改O(1)查询前缀和:维护整块前缀和与散块值,每次修改暴力修改所有在其之后的所有块实现O(sqrtn)单点修改O(1)查询。

O(1)单点修改O(sqrtn)查询前缀和:维护整块和与散块值,每次查询暴力加上所有在其之前的所有块实现O(1)单点修改O(sqrtn)查询。

至此我们可以实现所有分块+树状数组的复杂度平衡。对于其他数据结构,同样可以考虑用分块代替来平衡复杂度(当然并不是所有都可行)。

2、来自数论相关。

这个时候一般考虑预处理。乘法逆元、欧拉函数等基本都可以实现线性预处理O(1)查询。若来自FFT,那么诗乃不会。

快速幂和gcd都有支持预处理后O(1)查询的算法,在此不再赘述。

3、来自块内排序与块内二分。

若原题不支持离线,较难优化,视具体题目而定。

若支持离线,则可以离线后建立映射,用桶排序代替快速排序,同时维护块内桶的前缀和实现平衡。

4、来自其他

见机行事吧,不是所有都能平衡的。

3、根号分治

在莫队中有关数字出现次数的东西或其他可以根号分治的东西难以维护的时候可以用根号分治来解决。

例:(LuoguP5072)

珂朵莉给了你一个序列,每次查询一个区间[l,r]中所有子序列分别去重后的和mod p

分析可知假设这个数在[l,r]内出现了k次,则一共有2^(r-l+1)-2^(r-l+1-k)个子序列包含这个数。

每次统计答案时需要重新遍历计数数组,复杂度无法接受。此时可以通过根号下分类讨论将复杂度控制在O(sqrtn)之内。

4、缩小某个子问题的规模

例:求[l,r]中逆序对的个数。

不难想到莫队+树状数组的解法。发现这个修改次数和询问次数级别相同无法用2中的方法用分块代替,我们考虑减少询问/查询某一边的次数。

通过记录端点所需修改将所有端点的修改合到一起处理变成修改O(n)次查询O(nsqrt(n))次后,即可使用2中的方法平衡复杂度。详情百度莫队二次离线。

Extra:线段树的复杂度平衡

当线段树查询复杂度O(log^2n),修改复杂度O(logn)(或反过来的时候)

可以考虑改变线段树上每个节点的子节点个数来平衡复杂度。

例:单点修改,每个点修改复杂度为O(logn),区间查询。

发现每次修改的复杂度为O(logn*线段树层数),查询复杂度为O(线段树层数*线段树叉数)

一般线段树叉数为2,复杂度为一边O(log^2n),一边为O(logn)。

我们把线段树写成log叉即可平衡两边复杂度,为O(lognlogn/loglogn)。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00