この問題は Rolling Hash と呼ばれるハッシュアルゴリズムを利用するのが想定の問題です。Rolling Hash に関しては以前 ABC274 Ex の解説 でも解説したので、知らない方はそちらを参照してください。

まず、この問題では文字列の 1 点更新がクエリで入るため、一般的な文字列に関するデータ構造を利用するのは少し難しいです。そのため、セグメント木のようなデータ構造に回文に関する情報をうまく載せることを考えます。とはいえ、文字列をそのままセグメント木に載せると計算量が爆発してしまうので、ハッシュを情報として載せることにします。

長さ \(M\) の文字列 \(T = T_1 T_2 \dots T_M\) に対して \(T\) のハッシュ関数 \(H_1(T), H_2(T)\) を次のように定義します。
(式中の \(T_i\) は文字を ASCII コードなどの適当な数に置き換えたものとします。また、 \(p\) は素数、\(x\) は \(0\) 以上 \(p\) 未満の整数です。)

\[ \begin{aligned} H_1(T) &= \left( \sum_{i=1}^M T_i x^{M - i} \right) \bmod p \\ H_2(T) &= \left( \sum_{i=1}^M T_i x^{i - 1} \right) \bmod p \\ \end{aligned} \]

直感的には、\(H_1(T)\) は「文字列 \(T\) を左から Rolling Hash した時のハッシュ値」、\(H_2(T)\) は「文字列 \(T\) を右から Rolling Hash した時のハッシュ値」です。

このとき、\(T\) が回文であるならば \(H_1(T) = H_2(T)\) が成り立ちます。 また、\(T\) が回文でない場合は高確率で \(H_1(T) \neq H_2(T)\) が成り立ちます。(高く見積もっても\(1 - (M-1) / p\) 程度) よって、ハッシュ値を比較することで \(T\) が回文であるかを確率的に判定することが出来ます。
(\(p \simeq 10^9, M \simeq 10^6\) 程度の場合は \((p, x)\) の組が \(1\) 種類だけでは理論上の失敗確率は\(10^{-3}\) 程度と高めですが、例えば \((p, x)\) の組を \(4\) 種類選んで判定することで失敗確率を \(10^{-12}\) 程度まで下げることが出来ます。)

また、文字列 \(S\), \(T\) についてハッシュ値 \(H_1(S), H_2(S), H_1(T), H_2(T)\) が分かっているとき、文字列 \(S + T\) のハッシュは次のようになります。

\[ \begin{aligned} H_1(S + T) &= H_1(S) \times x^{|T|} + H_1(T) \\ H_2(S + T) &= H_2(S) + x^{|S|} \times H_2(T) \\ \end{aligned} \]

よって、文字列 \(S\) に対して \((H_1(S), H_2(S), x^{|S|})\) が対応するように情報を持つことにすると、この情報はセグメント木にうまく載せることができて、文字列の 1 点更新にも対応できます。

以上の内容を実装すればこの問題を \(\mathrm{O}(N + Q \log N)\) で解くことが出来て、これは十分高速です。

• 実装例(C++)

#include <array>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
using namespace std;
#include "atcoder/segtree.hpp"

constexpr int B = 5;
int mod[B] = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
int base[B];
struct Hash {
  long long h1, h2, pw;
};
using T = array<Hash, B>;

T op(T lhs, T rhs) {
  T res;
  for (int i = 0; i < B; i++) {
    res[i].h1 = (lhs[i].h1 * rhs[i].pw + rhs[i].h1) % mod[i];
    res[i].h2 = (lhs[i].h2 + lhs[i].pw * rhs[i].h2) % mod[i];
    res[i].pw = lhs[i].pw * rhs[i].pw % mod[i];
  }
  return res;
}
T e() {
  T res;
  for (int i = 0; i < B; i++) res[i] = {0, 0, 1};
  return res;
}
using SegTree = atcoder::segtree<T, op, e>;

T gen(char c) {
  T res;
  for (int i = 0; i < B; i++) res[i].h1 = res[i].h2 = c, res[i].pw = base[i];
  return res;
}

int main() {
  mt19937_64 rng(time(0));
  for (int i = 0; i < B; i++) base[i] = rng() % mod[i];

  cin.tie(0)->sync_with_stdio(0);
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<T> init(N);
  for (int i = 0; i < N; i++) init[i] = gen(S[i]);
  SegTree seg{init};

  while (Q--) {
    int cmd;
    cin >> cmd;
    if (cmd == 1) {
      int x;
      char c;
      cin >> x >> c;
      --x;
      seg.set(x, gen(c));
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      auto h = seg.prod(l, r);
      bool flag = true;
      for (int i = 0; i < B; i++) flag &= h[i].h1 == h[i].h2;
      cout << (flag ? "Yes" : "No") << endl;
    }
  }
}