倍增

zifuneko · 2024-05-26 18:22:24 · 算法·理论

归并排序、快速幂、慢速乘、逆元、倍增、分治与RMQ

归并排序

\text{sort}():

优点：快，时间复杂度 O(n\log n)

缺点：不稳定排序，只能做排序

归并排序：需要两个数组才能完成。

优点：时间稳定，时间复杂度 O(n\log n)，是稳定排序

缺点：空间较大

int a[1000005], b[1000005];
// 将a数组[l, r]区间排序
void gb(int l, int r)
{
    if(l >= r) return;

    int mid = (l+r)/2;
    gb(l, mid);
    gb(mid+1, r);

    int z=l, y=mid+1;
    // z代表左半部分开始位置
    for(int i=l; i<=r; i++)
    {
        //选出合适的数组放在b[i]里
        if(y>r || z<=mid && a[z] <= a[y])
        {
            b[i] = a[z];
            z++;
        }
        else
        {
            b[i] = a[y];
            y++;
        }
    }
    for(int i=l; i<=r; i++) a[i] = b[i];
}

快速幂

- $ (a+b)\mod p = (a\mod p + b\mod p) \mod p

(a-b)\mod p = (a\mod p - b\mod p + p) \mod p
(a\times b)\mod p = (a\mod p \times b\mod p) \mod p
a^b\mod p = (a\mod p)^b \mod p

分治法

long long p;
long long ksm(long long a, long long b)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans *= a;
            ans %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return ans;
}

慢速乘

主要目的：在乘法过程中防止溢出

long long mul(int a, int b)
{
    long long res = 0;
    while(b)
    {
        if(b & 1) ans = (ans + a) % p;
        a <<= 1;
        a %= p;
        b >>= 1;
    }
    return res;
}

逆元

同余

是数论中的重要概念。给定一个正整数 m ，如果两个整数 a 和 b 满足 a-b 能够被 m 整除，即 (a-b)\div m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a≡b(mod\ m)。对模 m 同余是整数的一个等价关系。

逆元

【定义】若在 mod\ p 意义下，对于一个整数 a ,有 a\times x ≡ 1\ (mod\ p)，那么这个整数 x 即为 a 的乘法逆元，同时 a 也为 x 的乘法逆元。

【充要条件】a 存在模 p 的乘法逆元的充要条件是 \gcd(a,p)=1 即 a 与 p 互质.

$\ \ \ \ \ a^p ≡ a(\mod p)

\ \ \ \ \ a^p \mod p = a \mod p \\= a^{p-1} ≡ 1 (\mod p)

如果 a 不是 p 的倍数，则 (a^{p-2})\mod p 就是 a 的逆元

a$ 的逆元：$(a^{p-2})\mod p

对于p是否为质数，我们可以分成两种求乘法逆元的方法。

1）当p为质数，可以用快速幂求逆元（费马小定理）

由费马小定理可知，当 p 为质数时

a^{p - 1}≡ 1 (mod\ p)

拆出一个 a 来可得：a \times a \times (p - 2) ≡ 1 (\mod p)

故当p为质数时，a的乘法逆元 x = a ^ {p - 2}

当然可能数 p - 2 很大，我们用快速幂来求解即可。

特例：

对于 a 是 p 的倍数的情况，其公约数时p，a和p肯定是不互质的，所以无解，即 ax\ \%\ p = 0

但是当a = 2， p = 2, a ^ {p - 2}= 2 ^{2 - 2} ≡ 1 \mod p

因此对于a = 2 ， p = 2 的情况需要特别判断一下（一般通过 a % p == 0 的方法判断掉）。

ST表

ST表（Sparse Table，稀疏表、倍增表）用于解决可重复贡献问题的数据结构。

ST表不仅可以处理区间最大值和最小值，还可以处理符合结合律和幂等律（与自身做运算，结果仍是自身）的信息查询。

例如「RMQ」,「区间按位与」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决。

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。

ST表可以做到 \Theta(n\log n) 预处理，\Theta(1) 回答每个询问。

令f(i,j) 代表以 i 开头的长度为 2^j 的区间的最大值，即区间 [i,i+2^j-1] 的最大值。
依据倍增的思想，可以写出状态转移方程 f(i,j) = \max (f(i,j-1), f(i+2^{j-1},j-1))。即区间 [i, i+2^{j}-1] 的最大值等于区间 [i, i+2^{j-1}-1] 的最大值与区间 [i+2^{j-1},i+2^j-1] 的最大值的最大值。
对于每个询问 [l,r]，我们把它分成两部分 [l,l+2^s-1] 与 [r-2^s+1,r]，其中 s=\left\lfloor\log_2(r-l+1)\right\rfloor。两部分的结果的最大值就是回答。重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 [l,r]，可以保证答案的正确性。

初始化及查询

void init()
{
    for(int i=1; i<=n; i++) st[i][0] = a[i];
    for(int j=1; (1<<j) <= n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    return;
}

int ask(int l, int r)
{
    int x = log2(r-l+1);
    return max(st[l][x] ,st[r-(1<<x)+1][x]);
}

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e6+5;
const int LOGMAX = 25;
int st[MAX][LOGMAX], logn[MAX];

void preLog()
{
    logn[1] = 0;
    logn[2] = 1;
    for(int i=3; i<MAX; i++) logn[i] = logn[i/2]+1; 
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    // 长度为1的区间最大值就是元素本身
    for(int i=1; i<=n; i++) cin >> st[i][0];
    // 递推构建ST表: 
    // st[i][j] = max(st[i][j-1], st[i+2^(j-1)][j-1])
    for(int j=1; (1<<j) <= n; j++)
        for(int i=1; i+(1<<j)-1 <= n; i++)
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);

    for(int i=1; i<=m; i++)
    {
        int l, r; cin >> l >> r;
        int s = log2(r - l + 1);
        cout << max(st[l][s] ,st[r-(1<<s)+1][s]) << endl;
    }
    return 0;
}

换底公式：\log_ab = \frac{\log_cb}{\log_ca}