小输入可用的子串最高频字母查询代码如何优化适配1e5次查询？

• 现有代码的时间复杂度是O(QN)*，N是字符串长度，Q是查询次数，当Q达到1e5、N=1e3时，总操作量会达到1e8级别，再加上每次查询内部多次遍历子串计数、使用map/set带来的额外开销，完全无法满足性能要求。

核心思路是前缀和预处理，利用只有26个小写字母的特性，提前计算每个字母的前缀出现次数，把单次查询的时间复杂度降到*O(1)*常数级（固定26次比较）：

1. 预处理阶段：创建二维前缀和数组pre[26][n+1]，其中pre[c][i]代表第c个小写字母在字符串S的前i个字符（下标0到i-1）中出现的总次数，预处理时间复杂度O(N26)*，N最大为1e3，开销可以忽略。
2. 查询阶段：对于每次查询的区间[x,y]，每个字母c的出现次数直接用pre[c][y+1] - pre[c][x]计算，遍历26个字母找出现次数最多、字典序最小的即可，单次查询仅需26次运算。

#include <bits/stdc++.h>
using namespace std;

int pre[26][1005]; // S长度最多1000，开1005足够覆盖边界

int main() {
    // 加速cin/cout，应对1e5次高频率输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    int n = s.size();
    // 预处理前缀和数组
    for (int i = 0; i < n; i++) {
        // 复制上一个位置的计数
        for (int c = 0; c < 26; c++) {
            pre[c][i+1] = pre[c][i];
        }
        // 当前字符对应计数+1
        pre[s[i] - 'a'][i+1]++;
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        int max_cnt = -1;
        char ans = 'z';
        // 从a到z遍历，相同计数下先遍历到的字典序更小，仅在计数更大时更新答案即可满足要求
        for (int c = 0; c < 26; c++) {
            int cnt = pre[c][y+1] - pre[c][x];
            if (cnt > max_cnt) {
                max_cnt = cnt;
                ans = 'a' + c;
            }
        }
        cout << ans << '\n'; // 用'\n'代替endl避免频繁刷新缓冲区，提升输出速度
    }
    return 0;
}

• 移除了所有冗余操作：不再创建子串、不再使用map/set存储字符、不再多次遍历子串计数，所有查询的计数操作都通过前缀和数组直接计算。
• 全链路优化输入输出性能：关闭cin和stdio同步、解除cin和cout的绑定，同时用'\n'代替endl，大幅提升1e5次输入输出的处理速度。

内容的提问来源于stack exchange，提问作者Zeros