# Segtree

[snippet/Segtree](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Segtree.hs)
は
[ACL](https://atcoder.jp/posts/517) の Segtree を移植したものである
（ただし、{min|max}_{left|right} は未実装）。

Segtree はモノイドに対して使用できるデータ構造である。
モノイドとは、以下を満たす代数構造である。

- 任意の \(a, b, c \in S\) に対して \((a \cdot b) \cdot c\ = a \cdot (b \cdot c)\) が成り立つ （結合律）
- 任意の \(a \in S\) に対して、\(a \cdot e = e \cdot a = a\) を満たすような \(e \in S\) が存在する（単位元の存在）

長さ \(N\) の列に対し、要素の 1 点変更、および、区間の要素の総積の取得をいずれも
\(\textrm{O}(\log N)\) で行うことができる。
（$<verb>{op}, $<verb>{e} がいずれも定数時間の場合）

$$<pre>{
data (PrimMonad m, Unbox a, Show a) => Segtree m a
$$}

Segtree は mutable なデータ構造で、IO または ST モナド上で用いることができる。
要素は Unboxed な値をとることが可能
（内部構造として [Data.Vector.Unboxed.Mutable](http://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Unboxed-Mutable.html#t:Unbox) を利用）である。
ライブラリのインタフェース上は、モノイドであることを明には要求していない。

## コンストラクタ (1)

コンストラクタは２種類ある。ひとつめは、長さ $<verb>{n} を指定して生成するものである。

$$<pre>{
newSEGT :: (PrimMonad m, Unbox a, Show a) => (a -> a -> a) -> a -> Int -> m (Segtree m a)
$$}

$<verb>{newSEGT op e n} のように、二項演算 $<verb>{op :: a -> a -> a}、
単位元 $<verb>{e :: a}　および要素数 $<verb>{n :: Int} を指定する。
これにより、長さ $<verb>{n} の数列 \(\{a_i\}\) が作られ、その初期値はすべて $<verb>{e}
となる。

### 制約

- \(0 \leq n \leq 10^8\)

### 計算量

- \(\textrm{O}(n)\)

## コンストラクタ (2)

ふたつめのコンストラクタは、初期値をベクターで与えるもの。

$$<pre>{
fromVecSEGT :: (PrimMonad m, Unbox a, Show a) => (a -> a -> a) -> a -> (V.Vector a) -> m (Segtree m a)
$$}

$<verb>{fromVecSEGT op e v} のように、
二項演算 $<verb>{op :: a -> a -> a}、
単位元 $<verb>{e :: a}　および初期値ベクトル $<verb>{v :: Data.Vector.Unboxed.Vector a} を指定する。
これにより、$<verb>{v} と同じ長さの数列 \(\{a_i\}\) が作られ、$<verb>{v} の内容が初期値となる。

### 制約

- \(0 \leq n \leq 10^8\)

### 計算量

- \(\textrm{O}(n)\)

## set

数列 \(\{a_i\}\) の１要素を変更する。

$$<pre>{
setSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> a -> m ()
$$}

$<verb>{setSEGT segtree p x} は、セグメント木 $<verb>{segtree} において数列の１要素 \(a_p\) の値を $<verb>{x} で置き換える。

### 制約

- \(0 \leq p < n\)

### 計算量

- \(\textrm{O}(\log n)\)

## get

数列の１要素の値を返す。

$$<pre>{
getSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> m a
$$}

$<verb>{getSEGT segtree p} は、
セグメント木 $<verb>{segtree} における数列の１要素 \(a_p\) の値を返す。

### 制約

- \(0 \leq p < n\)

### 計算量

- \(\textrm{O}(1)\)

## prod

指定された区間 \([l, r)\) の要素の総積

$$<pre>{
prodSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> Int -> Int -> m a
$$}

$<verb>{prodSEGT segtree l r} は、
$<verb>{a[l] `op` a[l+1] `op` ... `op` a[r-1]} を、
モノイドの性質を満たしていると仮定して計算する。
なお、\(l = r\) のときは $<verb>{e} を返す。

### 制約

- \(0 \leq l \leq r \leq n\)

### 計算量

- \(\textrm{O}(\log n)\)

## all_prod

全区間の総積

$$<pre>{
all_prodSEGT :: (PrimMonad m, Unbox a, Show a) => (Segtree m a) -> m a
$$}

$<verb>{a[0] `op` a[1] `op` ... `op` a[n-1]} を計算する。
\(n = 0\) のときは $<verb>{e} を返す。

### 計算量

- \(\textrm{O}(1)\)