首页 书籍 深入浅出程序设计竞赛(进阶篇) 分治与倍增

快速幂（Fast Power）是一种高效计算指数运算的算法。它利用指数的二进制表示来降低计算的时间复杂度。

假设要计算 a 的 n 次幂（a^n），其中 n 为非负整数。传统的方法是将 a 连乘 n 次，时间复杂度为 O (n)。而通过快速幂算法，我们可以将时间复杂度降低到 O (logn)。

快速幂算法的基本思想如下：

  1. 将指数 n 表示为二进制形式，例如 n=11 表示为 1011。
  2. 从二进制的最低位开始，依次处理每一位。
  3. 如果当前位为 1，则将结果累乘上底数 a。
  4. 每处理完一位，将底数 a 自乘，即 a=a^2。
  5. 继续处理下一位，直到所有位都被处理完毕。

下面是一个使用 C++ 实现的快速幂算法的示例代码：

#include <iostream>
using namespace std;
long long fastPower(int a, int n) {
    long long result = 1;
    long long base = a;
    while (n > 0) {
        if (n & 1) {
            result *= base;
        }
        base *= base;
        n >>= 1;
    }
    return result;
}
int main() {
    int a = 2;
    int n = 11;
    long long result = fastPower(a, n);
    cout << a << " raised to the power of " << n << " is: " << result << endl;
    return 0;
}
在这个例子中，我们使用了位运算和循环来实现快速幂算法。通过将指数 n 转化为二进制形式，并利用位运算的性质，我们可以在每一位上判断是否需要累乘底数 a。同时，在每一步中，底数 a 都会自乘，以便在下一位使用。


快速幂算法的时间复杂度为 O (logn)，其中 n 表示指数的大小。它是一种非常高效的算法，在指数运算问题中有广泛的应用，例如计算幂函数、矩阵的快速幂等。


ST 表（Sparse Table）是一种用于高效求解区间最值的数据结构。它利用了倍增的思想，通过预处理和查询操作，可以在 O (1) 的时间复杂度内求解任意区间的最大值或最小值。


ST 表的构建过程如下：


    

  1. 

    预处理：根据给定的数组，构建一个二维表格 dp [][]，其中 dp [i][j] 表示从位置 i 开始，长度为 2^j 的区间的最大值（或最小值）。
    

      

    • 当 j=0 时，dp [i][j] 就是数组中第 i 个元素本身。
      • 

    • 当 j>0 时，dp [i][j] 可以通过 dp [i][j-1] 和 dp [i+2^(j-1)][j-1] 两个子区间的最大值（或最小值）来计算，即 dp [i][j] = Max/Min (dp [i][j-1], dp [i+2^(j-1)][j-1])。
      • 

    

    2. 

  2. 

    查询：对于给定的查询区间 [left, right]，我们需要找到一个最大的 k，使得 2^k <= right - left + 1。然后，通过查表 dp [left][k] 和 dp [right-2^k+1][k] 来计算出区间 [left, right] 的最大值（或最小值）。
    

    3. 



下面是一个使用 ST 表求解区间最大值的示例代码：


#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 100005;  // 数组的最大长度
const int MAXLOG = 20;    //log2 (MAXN) 的上限
int dp[MAXN][MAXLOG];     // ST 表格
vector<int> arr;          // 输入的数组
// 构建 ST 表
void buildST(int n) {
    // 预处理第一列
    for (int i = 0; i < n; i++) {
        dp[i][0] = arr[i];
    }
    // 动态规划计算其他列
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            // 通过子区间的最大值计算当前区间的最大值
            dp[i][j] = max(dp[i][j-1], dp[i + (1 << (j-1))][j-1]);
        }
    }
}
// 查询区间最大值
int queryST(int left, int right) {
    int k = log2(right - left + 1);  // 找到 k 使得 2^k <= right - left + 1
    // 通过查表获取区间最大值
    return max(dp[left][k], dp[right - (1 << k) + 1][k]);
}
int main() {
    int n;
    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    buildST(n);  // 构建 ST 表
    int q;
    cin >> q;
    while (q--) {
        int left, right;
        cin >> left >> right;
        int maxVal = queryST(left, right);  // 查询区间最大值
        cout << "The maximum value in the range [" << left << ", " << right << "] is: " << maxVal << endl;
    }
    return 0;
}
在这个例子中，我们使用了 ST 表来求解给定查询区间内的最大值。首先，通过预处理构建了一个二维表格 dp [][]，其中存储了从不同位置开始、不同长度的区间的最大值。然后，根据查询区间的左右边界，通过查表来求解区间的最大值。


ST 表的构建时间复杂度为 O (nlogn)，其中 n 为数组的长度。每次查询的时间复杂度为 O (1)。ST 表适用于静态数组，即数组内容不会改变的情况下进行多次查询。


      

          
          
      

  


   


    

  
    
      
    
    更新于