百练百会 bestWit

Appearance

L8_04 倍增法 ​

一、倍增法的概念 ​

1.1 倍增法定义 ​

倍增法是一种基于二进制思想的算法，通过预处理将问题的时间复杂度从 O(n) 优化到 O(log n)。

1.2 倍增法的核心思想 ​

  • 将问题分解为若干个 2 的幂次部分
  • 通过预处理存储中间结果
  • 查询时通过二进制组合快速得到答案

1.3 倍增法的应用场景 ​

  • 求 LCA（最近公共祖先）
  • 区间 RMQ（范围最值查询）
  • 快速幂运算
  • 树上路径查询

二、快速幂 ​

2.1 快速幂算法 ​

cpp
// 计算 a^b mod modu
long long fastPow(long long a, long long b, long long modu) {
    long long result = 1;
    a %= modu;
    
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % modu;
        }
        a = (a * a) % modu;
        b >>= 1;
    }
    
    return result;
}

2.2 矩阵快速幂 ​

cpp
typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix& a, const Matrix& b, long long mod) {
    int n = a.size();
    Matrix result(n, vector<long long>(n, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    
    return result;
}

Matrix matrixPow(Matrix a, long long power, long long mod) {
    int n = a.size();
    Matrix result(n, vector<long long>(n, 0));
    
    // 初始化单位矩阵
    for (int i = 0; i < n; i++) {
        result[i][i] = 1;
    }
    
    while (power > 0) {
        if (power & 1) {
            result = multiply(result, a, mod);
        }
        a = multiply(a, a, mod);
        power >>= 1;
    }
    
    return result;
}

2.3 快速幂应用：斐波那契数列 ​

cpp
// 使用矩阵快速幂计算斐波那契数列第n项
long long fibonacci(long long n, long long mod) {
    if (n <= 1) return n;
    
    Matrix base = {{1, 1}, {1, 0}};
    Matrix result = matrixPow(base, n - 1, mod);
    
    return result[0][0];
}

三、区间 RMQ（倍增法） ​

3.1 RMQ 预处理 ​

cpp
const int MAXN = 100000;
const int LOG = 20;

int st[LOG][MAXN];
int logTable[MAXN];

void buildRMQ(const vector<int>& arr) {
    int n = arr.size();
    
    // 预处理 log 表
    logTable[1] = 0;
    for (int i = 2; i <= n; i++) {
        logTable[i] = logTable[i / 2] + 1;
    }
    
    // 初始化 ST 表
    for (int i = 0; i < n; i++) {
        st[0][i] = arr[i];
    }
    
    // 预处理倍增
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int queryRMQ(int l, int r) {
    int len = r - l + 1;
    int k = logTable[len];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

3.2 区间最大值查询 ​

cpp
void buildMaxRMQ(const vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n; i++) {
        st[0][i] = arr[i];
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int queryMaxRMQ(int l, int r) {
    int len = r - l + 1;
    int k = logTable[len];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

四、LCA（最近公共祖先） ​

4.1 LCA 预处理 ​

cpp
const int MAXN = 100000;
const int LOG = 20;

vector<int> adj[MAXN];
int depth[MAXN];
int up[LOG][MAXN];

void dfs(int u, int parent) {
    up[0][u] = parent;
    for (int v : adj[u]) {
        if (v != parent) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

void buildLCA(int root, int n) {
    depth[root] = 0;
    dfs(root, -1);
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n; i++) {
            if (up[j - 1][i] == -1) {
                up[j][i] = -1;
            } else {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }
    }
}

int lca(int u, int v) {
    // 确保 u 深度大于等于 v
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    
    // 将 u 提升到与 v 相同深度
    for (int j = LOG - 1; j >= 0; j--) {
        if (depth[u] - (1 << j) >= depth[v]) {
            u = up[j][u];
        }
    }
    
    if (u == v) return u;
    
    // 同时向上提升直到找到 LCA
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[j][u] != -1 && up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    }
    
    return up[0][u];
}

4.2 LCA 应用：树上距离 ​

cpp
int distance(int u, int v) {
    int ancestor = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[ancestor];
}

五、倍增法优化 DP ​

5.1 快速矩阵幂优化线性递推 ​

cpp
// 递推式：f(n) = a * f(n-1) + b * f(n-2)
long long linearRecurrence(long long n, long long a, long long b, long long mod) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    Matrix base = {{a, b}, {1, 0}};
    Matrix result = matrixPow(base, n - 1, mod);
    
    return result[0][0];
}

5.2 倍增法优化区间 DP ​

cpp
// 区间 DP 的倍增优化
// dp[i][j] 表示区间 [i, j] 的最优解

void buildIntervalDP(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 初始化长度为1的区间
    for (int i = 0; i < n; i++) {
        dp[i][i] = arr[i];
    }
    
    // 倍增预处理
    for (int len = 2; len <= n; len <<= 1) {
        for (int i = 0; i + len <= n; i++) {
            int mid = i + len / 2;
            dp[i][i + len - 1] = dp[i][mid - 1] + dp[mid][i + len - 1];
        }
    }
}

六、倍增法的应用 ​

6.1 二进制优化背包 ​

cpp
// 多重背包问题的二进制优化
int knapsackBinaryOptimization(vector<int>& weights, vector<int>& counts, 
                              vector<int>& values, int capacity) {
    vector<int> w, v;
    
    // 二进制拆分
    for (int i = 0; i < weights.size(); i++) {
        int cnt = counts[i];
        for (int j = 1; j <= cnt; j <<= 1) {
            w.push_back(weights[i] * j);
            v.push_back(values[i] * j);
            cnt -= j;
        }
        if (cnt > 0) {
            w.push_back(weights[i] * cnt);
            v.push_back(values[i] * cnt);
        }
    }
    
    // 0-1背包
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < w.size(); i++) {
        for (int j = capacity; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[capacity];
}

6.2 跳表 ​

cpp
// 跳表的倍增思想
class SkiplistNode {
public:
    int val;
    vector<SkiplistNode*> forward;
    
    SkiplistNode(int v, int level) : val(v), forward(level, nullptr) {}
};

class Skiplist {
private:
    SkiplistNode* head;
    int maxLevel;
    double p;
    
    int randomLevel() {
        int level = 1;
        while (rand() < RAND_MAX * p && level < maxLevel) {
            level++;
        }
        return level;
    }
    
public:
    Skiplist() : maxLevel(16), p(0.5) {
        head = new SkiplistNode(-1, maxLevel);
        srand(time(nullptr));
    }
    
    bool search(int target) {
        SkiplistNode* curr = head;
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < target) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        return curr && curr->val == target;
    }
    
    void add(int num) {
        SkiplistNode* curr = head;
        vector<SkiplistNode*> update(maxLevel);
        
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        
        int level = randomLevel();
        SkiplistNode* newNode = new SkiplistNode(num, level);
        
        for (int i = 0; i < level; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }
    
    bool erase(int num) {
        SkiplistNode* curr = head;
        vector<SkiplistNode*> update(maxLevel);
        
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        
        curr = curr->forward[0];
        if (!curr || curr->val != num) return false;
        
        for (int i = 0; i < maxLevel; i++) {
            if (update[i]->forward[i] != curr) break;
            update[i]->forward[i] = curr->forward[i];
        }
        
        delete curr;
        return true;
    }
};

七、倍增法复杂度分析 ​

操作预处理时间查询时间空间复杂度
快速幂O(1)O(log n)O(1)
RMQO(n log n)O(1)O(n log n)
LCAO(n log n)O(log n)O(n log n)
矩阵快速幂O(1)O(k³ log n)O(k²)

其中 k 为矩阵大小。

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5