そもそも，おなじ `primstate` に対して， `primstate ~ PrimState m` となるような `PrimMonad` である `m` はたくさん存在する，と言うのが問題ですよね．例えば，`primstate ~ RealWorld` の時点で
```PrimState (ST RealWorld) = RealWorld
PrimState IO = RealWorld
PrimState (MaybeT IO) = RealWorld```
`IO` と `ST` の時点で重複があるので， `M RealWorld` を一つに定めるのは不可能です．ふつうに `ST RealWorld` を使うこともありますしね．だから， `M primstate` という型族を用いるのが良くないのでは，という気がしています．
例えば:
```{-# LANGUAGE MultiParamTypeClasses #-}
class Monad m => SegmentTree a m where
updateParent :: a -> Int -> Int -> m Int
....
instance PrimMonad m => SegmentTree (RMQ (PrimState m)) m where ...```
とか，
```{-# LANGUAGE MultiParamTypeClasses #-}
class Monad m => SegmentTree a m where
updateParent :: a -> Int -> Int -> m Int
....
instance SegmentTree (RMQ s) (ST s) where ...
instance SegmentTree (RMQ RealWorld) IO where ...```
とか，
```class SegmentTree f where
updateParent :: PrimMonad m => f (PrimState m) -> Int -> Int -> m Int
...
instance SegmentTree RMQ where ...```
とか．
また，コードでは `RMQ s` とか `RMQ RealWorld` とかやって使うようになっていますが，質問文のように `RMQ IO` とか `RMQ (ST s)` とかやって使うとすれば:
```class SegmentTree f where
updateParent :: PrimMonad m => f m -> Int -> Int -> m Int
...
instance SegmentTree RMQ where ...```
とかもあります．`RMQ RealWorld` バージョン にも私が思いつくだけで変種が三種類ありましたが， `RMQ IO` バージョンにも同じような変種がありますね．