

倍增

Copyright

本页面贡献者：freshman_lcx。 本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

倍增思想

给定一个长度为N的数列A，然后进行若干次询问，每给定一个正整数T，求出最大的 k ， $\sum_{i=1}^k {A[i]}\leq T$ 。你的算法必须是在线的，假设 $0 \leq T \leq \sum_{i=1}^k {A[i]}$ 。

我们可以设计这样一种倍增算法：

先花费O(N)的时间预处理出前缀和数组S

1、令 p=1，k=0，sum=0;

2、比较“A数组中 k 之后的 p 个数的和加上sum”与 T 的关系，也就是说，如果 sum+S[k+p]-S[k]<=T ，则令 sum+=S[k+p]-S[k] , k+=p , p*=2 , 即累加上这p个数的和，然后把 p 的跨度增长一倍。如果 sum+S[k+p]-S[k]>T,则令 p/=2。

3、重复上一步，直到 p 的值变为 0 ，此时 k 就是答案。

int n,A[maxn],T,S[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        S[i]=A[i]+S[i-1];
    }
    while(cin>>T)
    {
        int p=1,k=0,sum=0;
        while(p!=0)
        {
            if(sum+S[k+p]-S[k]<=T)
            {
                sum+=S[k+p]-S[k];
                k+=p;
                p*=2;
            }
            else
                p/=2;
        }
        cout<<k<<endl;
    }
    return 0;
}

倍增的应用

最近公共祖先(lca)

利用二进制的思想，想办法使一步一步向上搜索变成以 $2^{k}$ 的向上跳。所以定义一个f[][]数组，使f[j][i]表示节点i的 $2^{j}$ 倍祖先。

快速幂

给出x，y，p，求 $x^{y}$%p，如果x,y的数据很大的话，O(n)的算法会超时，那么这时候我们可以用倍增的方法减少运算次数

先求出

$x^{1}$ $x^{2}$ $x^{4}$ $x^{8}$.....(不过几十次运算)

对于任意一个y, $x^{y}$ 都可以由上面的项做乘积得到（也不过是几十次运算）

这样就大大减少了运算次数

RMQ求区间最值问题

给出n个数组成的数列，q次询问，每次给出x，y问x~y之间的最小值是多少？

如果直接暴力的话复杂度O(n*q)

RMQ算法也是用到了倍增的方法

f(i,1)表示从第i个位置开始，往后1个数的最小值

f(i,2)表示从第i个位置开始，往后2个数的最小值

f(i,3)表示从第i个位置开始，往后4个数的最小值

则递推式即为f(i,k)=min(f(i,k-1),f(i+$2^{k-2}$,k-1))

时间复杂度为 $O(n*logn+q)$