使用倍增算法,要求递推的问题的状态空间关于 2 的次幂具有可划分性
在进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间的要求
那么我们可以通过倍增的方式,只递推状态空间中在 2 的整数次幂位置上的值作为代表
当需要其他位置上的值时,我们通过 “任意整数可以表示成若干个 2 的次幂项的和” 这一性质,使用之前求出的代表值拼成所需的值
“倍增” 与 “二进制划分” 两个思想相互结合,降低了求解很多问题的空间与时间复杂度(例如:快速幂)
本节会讲解的内容:序列上的倍增问题,求解RMQ问题的ST表算法
后续树的章节还会介绍树上倍增求LCA
试想这样一个问题:
给定一个长度为
的序列
,然后进行若干次询问,每次给定一个整数
,求出最大的
,满足
。
算法要求强制在线,且
最朴素的做法是从前往后枚举
,每次询问花费的时间与答案的大小有关,最坏时间复杂度为
通过简单观察发现,答案具有单调性,因此处理单次询问可以 “二分答案转化为判定”
又观察到每次判定,要用到前缀区间的元素和,因此想到再预处理出一个前缀和优化判定
这样做,处理单词询问的时间复杂度为:
二分的解法在平均意义下表现很好,但是缺点在于如果每次询问给定的整数
非常小,导致答案
也很小,那么该算法可能还不如从前往后枚举更优
于是可以设计出这样一种倍增算法:
,
,
,其中
为 2 次幂跨度,
为当前前缀下标,
为当前前缀和
数组中
之后的
个数的和” 与 “
” 的关系
,则令 sum += s[k + p] - s[k], k += p, p *= 2
即累加上这一段,并让
的跨度增长一倍
,则令 p /= 2
的值变为
,此时
即为答案
int p = 1, k = 0, sum = 0;
while (p)
{
if (sum + s[k + p] - s[k] <= T)
{
sum += s[k + p] - s[k];
k += p;
p *= 2;
}
else p /= 2;
}
这个算法始终在答案大小的范围内实施 “倍增” 与 “二进制划分” 思想,通过若干长度为
的次幂的区间拼成最后的
,时间复杂度为
,能够应对
的各种大小情况。
而且序列上倍增还有一个规律,就是一开始
连续成倍增长,之后
连续折半递减。
RMQ的经典应用就是ST表算法,很多人可能只知道RMQ,却不知道其就是倍增的一种产物
给定一个长度为
的序列
,ST算法能在
时间的预处理后,以
的时间在线处理 “序列
的下标在
之间的数的最值是多少” 这样的区间最值询问
一个序列的子区间个数为
个,根据倍增的思想,首先在这
个状态空间里选择一些
的整数次幂的位置作为代表值
设
表示序列
的子区间
里的最值
即从
开始(包括
) 的
个数的最大值
问题的边界显然是
,递推式为:
即区间
的最大值为区间
与区间
的最大值
再考虑一下
的范围:极限情况下是求区间
的最值,于是有
化简易得:
void ST_prework()
{
for (int i = 1; i <= n; i ++ ) f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; j ++ )
for (int i = 1; i <= n - (1 << j) + 1; i ++ )
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
当询问区间
时,先计算出
,满足
,即小于区间长的最大
的
次幂
这样保证两个子区间:
和
一定能覆盖住区间
两个区间的最大值的最大值,即为整个区间的最大值
int ST_query(int l, int r)
{
int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
log
函数为cmath
库里的函数,因为其效率很高,因此我们近似看成
无碍
给定一个整数
,对于任意一个整数集合
,定义“校验值”如下:
从集合
中取出
对数(即
个数,不能重复使用集合中的数,如果
中的整数不够
对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合
的“校验值”。
现在给定一个长度为
的数列
以及一个整数
我们要把
分成若干段,使得每一段的“校验值”都不超过
求最少需要分成几段
输入格式
第一行输入整数
,代表有
组测试数据
对于每组测试数据,第一行包含三个整数
,
,
第二行包含
个整数,表示数列
输出格式
对于每组测试数据,输出其答案,每个答案占一行
数据范围
,
,
,
输入样例:
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
输出样例:
2
1
先考虑如何求一个集合的校验值?
结论:选出
个最大值和
个最小值,然后最大值配对最小值,次大值配对次小值 ......
证明:假设排序后的
个数为
按照上述策略配对,有:
考虑交换配对
和
,其中
故有大小关系:
,校验值为:
交换配对后,有两种情况,第一种情况为:
和
其校验值为:
,两个等式作差易得:
交换之后,显然方案不会变差,第二种情况为:
和
其校验值为:
,两个等式作差易得:
交换之后,显然方案不会变差
考虑如何分段?
由于题设要求是分成的段数尽可能少,因此每段要求尽可能长,这就与“序列前缀区间和询问”一样了
不过那一题是求前缀区间和不少于
,这一题是前缀校验值不少于
这题就会体现出 “倍增” 和 “二分” 的区别了
由于每次要判定当前的答案是否满足条件,因此每次判定,都要对答案区间进行排序,然后配对
“倍增” 和 “二分” 找答案的时间复杂度基本一致,差的只是常数,但问题主要出现在答案判定上
如果用二分,每一次二分的中点就是
,这个
与
是一个数量级的
因此如果答案的每个段很小,那么每次排序复杂度为
,总复杂度是
如果用 “倍增” 寻找答案,他会从小区间往大区间扩展,效率高于二分,这里可以给出数学证明:
假设倍增到答案过程中判定的区间长度分别为:
,先考虑单次分段倍增的复杂度:
将所有的段加起来,总的时间复杂度为:
远远优于二分做法
倍增过程如下:
,
这一段区间的校验值:
,则 R += p, p *= 2
,则 p /= 2
变为
为止,此时
即为所求
bool check(int l, int r)
{
int k = 0;
for (int i = l; i < r; i ++ ) b[k ++ ] = a[i];
sort(b, b + k);
LL sum = 0;
for (int i = 0; i < m && i < k; i ++ , k -- )
sum += (LL) (b[i] - b[k - 1]) * (b[i] - b[k - 1]);
return sum <= T;
}
void solve()
{
scanf("%d%d%lld", &n, &m, &T);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int l = 0, cnt = 0;
while (l < n)
{
int p = 1, r = l;
while (p)
{
if (r + p <= n && check(l, r + p))
{
r += p;
p *= 2;
}
else p /= 2;
}
cnt ++ ;
l = r;
}
printf("%d\n", cnt);
}
不难发现,在倍增的过程中,排序的片段中前缀数组已经有序(因为上一轮倍增好后排好了)
即
已经有序,现在倍增需要检验的区间为
如上面的做法,采用直接对
区间排序的策略,最终的时间复杂度为
既然前缀区间已有序,不妨只排
,再将两个区间做一次 二路归并,单次分段的时间复杂度如下:
这样总的时间复杂度为:
,是本题的最优解
bool check(int l, int mid, int r)
{
for (int i = mid; i < r; i ++ ) b[i] = a[i];
sort(b + mid, b + r);
int i = l, j = mid, k = 0;
while (i < mid && j < r)
{
if (b[i] < b[j]) t[k ++ ] = b[i ++ ];
else t[k ++ ] = b[j ++ ];
}
while (i < mid) t[k ++ ] = b[i ++ ];
while (j < r) t[k ++ ] = b[j ++ ];
LL sum = 0;
for (int i = 0; i < m && i < k; i ++ , k -- )
sum += (LL) (t[i] - t[k - 1]) * (t[i] - t[k - 1]);
return sum <= T;
}
void solve()
{
scanf("%d%d%lld", &n, &m, &T);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int l = 0, cnt = 0;
while (l < n)
{
int p = 1, r = l;
while (p)
{
if (r + p <= n && check(l, r, r + p))
{
r += p;
p *= 2;
for (int i = l; i < r; i ++ )
b[i] = t[i - l];
}
else p /= 2;
}
cnt ++ ;
l = r;
}
printf("%d\n", cnt);
}