ST 表-区间求最值

admin

结构体定义：
使用template <typename T>声明泛型结构体，支持多种数据类型
成员变量st用于存储各级区间的最值
成员变量log_table预计算 log2 值，加速查询过程
核心原理：
预处理阶段：通过动态规划构建多级区间最值表，每一级的区间长度是上一级的 2 倍
查询阶段：对于任意区间，找到两个长度为 2^k 的子区间覆盖它，取这两个子区间的最值作为结果
与类实现的区别：
结构体默认成员为公有，不需要显式声明 public 访问修饰符
更轻量的封装，适合简单的数据结构实现
功能上与类实现完全一致，都能高效处理区间最值查询
示例说明
代码中包含两个测试函数：
test_int_array()：演示对整数数组的区间最小值查询
test_double_array()：演示对浮点数数组的区间最小值查询

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 定义ST表结构体，使用模板支持多种数据类型
template <typename T>
struct SparseTable {
    // st[k][i]表示从位置i开始，长度为2^k的区间的最值
    vector<vector<T>> st;
    // 预计算log2值，加速查询过程
    vector<int> log_table;
    
    // 构造函数，根据输入数组初始化ST表
    SparseTable(const vector<T>& arr) {
        int n = arr.size();
        if (n == 0) return;
        
        // 计算最大层数，log2(n)向上取整加1
        int max_level = log2(n) + 1;
        st.resize(max_level, vector<T>(n));
        log_table.resize(n + 1);
        
        // 初始化第0层，区间长度为1（2^0）
        for (int i = 0; i < n; ++i) {
            st[0][i] = arr[i];
        }
        
        // 预计算log2值，用于快速确定查询时的区间长度
        log_table[1] = 0;
        for (int i = 2; i <= n; ++i) {
            log_table[i] = log_table[i / 2] + 1;
        }
        
        // 构建ST表，填充各层数据
        // k表示当前层数，对应的区间长度为2^k
        for (int k = 1; k < max_level; ++k) {
            // 确保区间不超出数组范围
            for (int i = 0; i + (1 << k) <= n; ++i) {
                // 合并两个子区间的最值
                // 子区间1: [i, i + 2^(k-1) - 1]
                // 子区间2: [i + 2^(k-1), i + 2^k - 1]
                st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]);
            }
        }
    }
    
    // 区间查询函数，返回[l, r]区间内的最小值
    T query(int l, int r) const {
        // 确保查询区间的合法性
        if (l > r) swap(l, r);
        if (l < 0 || r >= st[0].size()) {
            cerr << "查询区间超出范围!" << endl;
            return T(); // 返回该类型的默认值
        }
        
        // 计算区间长度
        int len = r - l + 1;
        // 计算最大的k，使得2^k <= len
        int k = log_table[len];
        
        // 合并两个覆盖整个查询区间的子区间
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

// 示例：查询整数数组的区间最小值
void test_int_array() {
    cout << "=== 整数数组测试 ===" << endl;
    vector<int> arr = {5, 3, 8, 1, 6, 9, 2, 7};
    
    // 创建ST表结构体实例
    SparseTable<int> st(arr);
    
    // 输出原始数组
    cout << "原始数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl << endl;
    
    // 测试不同区间的查询
    cout << "区间[0, 3]的最小值: " << st.query(0, 3) << endl;  // 结果应为1
    cout << "区间[2, 5]的最小值: " << st.query(2, 5) << endl;  // 结果应为1
    cout << "区间[4, 7]的最小值: " << st.query(4, 7) << endl;  // 结果应为2
    cout << "区间[1, 1]的最小值: " << st.query(1, 1) << endl;  // 结果应为3
    cout << endl;
}

// 示例：查询浮点数数组的区间最小值
void test_double_array() {
    cout << "=== 浮点数数组测试 ===" << endl;
    vector<double> arr = {3.14, 1.59, 2.65, 0.89, 4.71, 2.36};
    
    // 创建ST表结构体实例
    SparseTable<double> st(arr);
    
    // 输出原始数组
    cout << "原始数组: ";
    for (double num : arr) {
        cout << num << " ";
    }
    cout << endl << endl;
    
    // 测试不同区间的查询
    cout << "区间[0, 5]的最小值: " << st.query(0, 5) << endl;  // 结果应为0.89
    cout << "区间[1, 3]的最小值: " << st.query(1, 3) << endl;  // 结果应为0.89
    cout << "区间[2, 4]的最小值: " << st.query(2, 4) << endl;  // 结果应为0.89
    cout << endl;
}

int main() {
    // 测试整数数组
    test_int_array();
    
    // 测试浮点数数组
    test_double_array();
    
    return 0;
}
    

admin

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

// 定义最大数组大小和最大层数，根据实际需求调整
#define MAX_N 10000    // 最大元素数量
#define MAX_LOG 20     // 最大层数，2^20足够覆盖10000元素

// 定义ST表结构体，仅用于整数数组
struct SparseTable {
    // st[k][i]表示从位置i开始，长度为2^k的区间的最小值
    int st[MAX_LOG][MAX_N];
    // 预计算log2值，加速查询过程
    int log_table[MAX_N + 1];
    // 实际元素数量
    int n;
    
    // 构造函数，根据输入数组初始化ST表
    SparseTable(int arr[], int size) {
        n = size;
        if (n == 0) return;
        
        // 初始化第0层，区间长度为1（2^0）
        for (int i = 0; i < n; ++i) {
            st[0][i] = arr[i];
        }
        
        // 预计算log2值，用于快速确定查询时的区间长度
        log_table[1] = 0;
        for (int i = 2; i <= n; ++i) {
            log_table[i] = log_table[i / 2] + 1;
        }
        
        // 计算最大层数，log2(n)向上取整
        int max_level = log_table[n] + 1;
        
        // 构建ST表，填充各层数据
        // k表示当前层数，对应的区间长度为2^k
        for (int k = 1; k < max_level; ++k) {
            // 确保区间不超出数组范围
            for (int i = 0; i + (1 << k) <= n; ++i) {
                // 合并两个子区间的最小值
                // 子区间1: [i, i + 2^(k-1) - 1]
                // 子区间2: [i + 2^(k-1), i + 2^k - 1]
                st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]);
            }
        }
    }
    
    // 区间查询函数，返回[l, r]区间内的最小值（0-based索引）
    int query(int l, int r) const {
        // 确保查询区间的合法性
        if (l > r) swap(l, r);
        if (l < 0 || r >= n) {
            cerr << "查询区间超出范围!" << endl;
            return 0; // 非法查询返回0
        }
        
        // 计算区间长度
        int len = r - l + 1;
        // 计算最大的k，使得2^k <= len
        int k = log_table[len];
        
        // 合并两个覆盖整个查询区间的子区间
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

// 示例测试函数
void test_st_table() {
    cout << "=== 整数数组ST表测试 ===" << endl;
    
    // 测试数组
    int arr[] = {5, 3, 8, 1, 6, 9, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    // 创建ST表结构体实例
    SparseTable st(arr, size);
    
    // 输出原始数组
    cout << "原始数组: ";
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl << endl;
    
    // 测试不同区间的查询
    cout << "区间[0, 3]的最小值: " << st.query(0, 3) << endl;  // 结果应为1
    cout << "区间[2, 5]的最小值: " << st.query(2, 5) << endl;  // 结果应为1
    cout << "区间[4, 7]的最小值: " << st.query(4, 7) << endl;  // 结果应为2
    cout << "区间[1, 1]的最小值: " << st.query(1, 1) << endl;  // 结果应为3
    cout << "区间[0, 7]的最小值: " << st.query(0, 7) << endl;  // 结果应为1
}

int main() {
    // 运行测试
    test_st_table();
    
    return 0;
}