c++算法学习7——倍增算法

一、什么是倍增算法？

倍增算法是一种基于分治思想和二进制拆分的高效算法，主要用于解决区间查询问题。它的核心思想是通过预处理数据，构建一个信息表，使得我们能够在常数时间内回答任意区间的查询请求。

倍增算法的核心原理

1. 预处理阶段：

   • 从原始数据开始，构建以每个位置为起点、长度为2⁰（即1）的区间信息

   • 基于上一级信息，构建长度为2¹、2²、2³...的区间信息

   • 通过合并相邻区间信息，形成倍增的信息表

2. 查询阶段：

   • 将任意查询区间分解为两个预处理的区间

   • 合并这两个区间的信息得到最终结果

   • 整个过程在O(1)时间内完成

二、经典应用：区间最小值查询(RMQ)

1.问题描述

给定一个长度为m的数组，需要快速回答多个查询：在区间[a, b]中的最小值是多少？

2.倍增算法实现

数据结构定义

const int M = 1e5 + 5;
int a[M];       // 原始数据
int log[M];     // 预处理的log2值
int f[M][20];   // 倍增信息表

预处理过程

void rmq_init() {log[0] = -1;  // 特殊初始化// 计算log2(i)的整数部分for(int i = 1; i <= m; i++) {log[i] = log[i / 2] + 1;  // 递推计算log2值f[i][0] = a[i];           // 初始化：长度为1的区间}// 构建倍增表for(int j = 1; j <= log[m]; j++) {for(int i = 1; i + (1 << j) - 1 <= m; i++) {// 合并两个2^{j-1}长度的区间f[i][j] = min(f[i][j-1], f[i + (1 << (j-1))][j-1]);}}
}

查询过程

int query(int l, int r) {int len = log[r - l + 1];  // 计算区间长度的log2值// 合并两个2^len长度的区间return min(f[l][len], f[r - (1 << len) + 1][len]);
}

算法分析

• 时间复杂度：

  • 预处理：O(m log m)

  • 查询：O(1)

• 空间复杂度：O(m log m)

• 优势：应对大量查询时效率极高

三、实际应用：忠诚的管家

1.题目描述：

老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自己账目 更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十 分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用 一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3...编号，然后不定时的问管家问题，问题是这样的:在a到b号账中最少的一笔是多少?为了让 管家没时间作假他总是一次问多个问题。

输入格式：第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题 n<=100000。

                  第二行为m个数,分别是账目的钱数 后面n行分别是n个问题,每行有2个数字说明开始结                    束的账目编号。

输出格式：输出文件中为每个问题的答案。具体查看样例。

输入样例：10 3

                  2 1 9 4 5 6 10 8 3 7 

                  2 7

                  3 9

                  1 10

输出样例：1 3 1

2.解决方案

#include <iostream>
#include <algorithm>
using namespace std;const int M = 1e5 + 5;
int m, n;
int a[M], log_val[M], f[M][20];void rmq_init() {log_val[0] = -1;for (int i = 1; i <= m; i++) {log_val[i] = log_val[i / 2] + 1;f[i][0] = a[i];}for (int j = 1; j <= log_val[m]; j++) {for (int i = 1; i + (1 << j) - 1 <= m; i++) {f[i][j] = min(f[i][j-1], f[i + (1 << (j-1))][j-1]);}}
}int query(int l, int r) {int k = log_val[r - l + 1];return min(f[l][k], f[r - (1 << k) + 1][k]);
}int main() {cin >> m >> n;for (int i = 1; i <= m; i++) cin >> a[i];rmq_init(); // 预处理for (int i = 1; i <= n; i++) {int l, r;cin >> l >> r;cout << query(l, r) << " ";}return 0;
}

四、进阶应用：滑动窗口最小值

1.问题描述

给定一个长度为n的数列和一个整数m，对每个位置i（从1到n），求区间[max(1, i-m), i-1]中的最小值。

2.倍增算法实现

#include <iostream>
#include <cstdio>
using namespace std;const int maxn = 2000005;
int a[maxn], log_val[maxn], f[maxn][20];int main() {int n, m;scanf("%d%d", &n, &m);// 输入序列for (int i = 1; i <= n; i++) scanf("%d", &a[i]);// 初始化log数组log_val[0] = -1;for (int i = 1; i <= n; i++) {log_val[i] = log_val[i / 2] + 1;f[i][0] = a[i];}printf("0\n"); // 第一个位置前无元素int current = 2; // 从第二个位置开始处理for (int j = 1; (1 << j) <= n; j++) {// 构建倍增表for (int i = 1; i + (1 << j) - 1 <= n; i++) {f[i][j] = min(f[i][j-1], f[i + (1 << (j-1))][j-1]);}// 处理所有右边界为current的查询while (current <= n && min(current - 1, m) < (1 << (j + 1))) {int l = max(1, current - m);int r = current - 1;int len = log_val[r - l + 1];printf("%d\n", min(f[l][len], f[r - (1 << len) + 1][len]));current++;}}// 处理剩余查询while (current <= n) {int l = max(1, current - m);int r = current - 1;int len = log_val[r - l + 1];printf("%d\n", min(f[l][len], f[r - (1 << len) + 1][len]));current++;}return 0;
}

3.算法特点

1. 按需构建：不是一次性构建完整的倍增表，而是根据需要逐步构建

2. 高效处理：每个查询在O(1)时间内完成

3. 空间优化：只构建当前需要的部分倍增表

五、倍增算法与其他算法的比较

算法	预处理时间	查询时间	空间复杂度	适用场景
倍增算法	O(n log n)	O(1)	O(n log n)	静态数据，大量查询
线段树	O(n)	O(log n)	O(n)	动态数据，支持修改
树状数组	O(n)	O(log n)	O(n)	前缀和查询，支持更新
朴素算法	O(1)	O(n)	O(n)	少量查询