Dynamic String(Point Set)

Fenwick Tree(Binary Indexed Tree)上でRolling hashの計算を行うとクエリあたり $O(logN)$ で1点更新, 区間のハッシュを求めることができます.

タイプ2のクエリでは, 二分探索で区間のハッシュが一致しなくなる点を探すことでクエリあたり $O(logN log(min(N, M)))$ で計算できます.

Tが静的な文字列であり, 前処理を行っておくと区間のハッシュが $O(1)$ で求められることを利用すると, Fenwick Tree上の二分探索によりクエリあたり $O(logN)$ に高速化できます