【算法精讲】洛谷P2412 区间最大字典序查询：ST表高效解法与C++实现
一、SEO化题目解读
洛谷P2412是一道字符串处理与区间查询结合的题目，要求在多个查询区间内找到字典序最大的字符串（不区分大小写）。题目考察ST表（稀疏表）数据结构的应用，是学习高效区间查询算法的典型案例。
二、解题思路（参考代码分析）
三、解题步骤详解
输入处理：读取字符串数量和查询数量
预处理阶段：
构建所有字符串的小写版本
初始化ST表第一层
动态填充ST表各层
查询阶段：
计算查询区间的长度
分解区间为两个已知区间
比较并返回结果
结果输出：直接输出查询结果
四、完整代码实现
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
// 构建ST表
vector<vector<int>> buildST(const vector<string>& words) {
int n = words.size();
int k = log2(n) + 1;
vector<vector<int>> st(n, vector<int>(k));
// 预处理小写版本避免重复转换
vector<string> lower_words(n);
for(int i = 0; i < n; ++i) {
lower_words[i].resize(words[i].size());
transform(words[i].begin(), words[i].end(),
lower_words[i].begin(), ::tolower);
}
for(int i = 0; i < n; ++i) st[i][0] = i;
for(int j = 1; (1<<j) <= n; ++j) {
for(int i = 0; i + (1<<j) - 1 < n; ++i) {
int x = st[i][j-1];
int y = st[i+(1<<(j-1))][j-1];
st[i][j] = (lower_words[x] > lower_words[y] ||
(lower_words[x] == lower_words[y] && x > y)) ? x : y;
}
}
return st;
}
// ST表查询函数
int query(const vector<vector<int>>& st, const vector<string>& words,
const vector<string>& lower_words, int l, int r) {
int len = r - l + 1;
int j = log2(len);
int x = st[l][j];
int y = st[r - (1<<j) + 1][j];
return (lower_words[x] > lower_words[y] ||
(lower_words[x] == lower_words[y] && x > y)) ? x : y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> words(n);
for(int i = 0; i < n; ++i) {
cin >> words[i];
}
auto st = buildST(words);
vector<string> lower_words(n);
for(int i = 0; i < n; ++i) {
lower_words[i].resize(words[i].size());
transform(words[i].begin(), words[i].end(),
lower_words[i].begin(), ::tolower);
}
while(m--) {
int x, y;
cin >> x >> y;
x--; y--;
int pos = query(st, words, lower_words, x, y);
cout << words[pos] << '\n';
}
return 0;
}五、总结
本文详细解析了洛谷P2412的ST表解法，通过预处理和空间换时间的策略，将区间查询时间复杂度优化到O(1)。该算法特别适合处理静态数据的多次区间查询问题，是竞赛编程中常用的高效算法之一。
原创内容 转载请注明出处
