snippet/Segtree は ACL の Segtree を移植したものである （ただし、{min|max}_{left|right} は未実装）。
Segtree はモノイドに対して使用できるデータ構造である。 モノイドとは、以下を満たす代数構造である。
長さ \(N\) の列に対し、要素の 1 点変更、および、区間の要素の総積の取得をいずれも \(\textrm{O}(\log N)\) で行うことができる。 （op , e がいずれも定数時間の場合）
data (PrimMonad m, Unbox a, Show a) => Segtree m a
Segtree は mutable なデータ構造で、IO または ST モナド上で用いることができる。 要素は Unboxed な値をとることが可能 （内部構造として Data.Vector.Unboxed.Mutable を利用）である。 ライブラリのインタフェース上は、モノイドであることを明には要求していない。
コンストラクタは２種類ある。ひとつめは、長さ n を指定して生成するものである。
newSEGT :: (PrimMonad m, Unbox a, Show a) => (a -> a -> a) -> a -> Int -> m (Segtree m a)
newSEGT op e n のように、二項演算 op :: a -> a -> a 、 単位元 e :: a および要素数 n :: Int を指定する。 これにより、長さ n の数列 \(\{a_i\}\) が作られ、その初期値はすべて e となる。
ふたつめのコンストラクタは、初期値をベクターで与えるもの。
fromVecSEGT :: (PrimMonad m, Unbox a, Show a) => (a -> a -> a) -> a -> (V.Vector a) -> m (Segtree m a)
fromVecSEGT op e v のように、 二項演算 op :: a -> a -> a 、 単位元 e :: a および初期値ベクトル v :: Data.Vector.Unboxed.Vector a を指定する。 これにより、v と同じ長さの数列 \(\{a_i\}\) が作られ、v の内容が初期値となる。
数列 \(\{a_i\}\) の１要素を変更する。
setSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> a -> m ()
setSEGT segtree p x は、セグメント木 segtree において数列の１要素 \(a_p\) の値を x で置き換える。
数列の１要素の値を返す。
getSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> m a
getSEGT segtree p は、 セグメント木 segtree における数列の１要素 \(a_p\) の値を返す。
指定された区間 \([l, r)\) の要素の総積
prodSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> Int -> m a
prodSEGT segtree l r は、 a[l] `op` a[l+1] `op` ... `op` a[r-1] を、 モノイドの性質を満たしていると仮定して計算する。 なお、\(l = r\) のときは e を返す。
全区間の総積
all_prodSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> m a
a[0] `op` a[1] `op` ... `op` a[n-1] を計算する。 \(n = 0\) のときは e を返す。