"遅延伝播" の一般化

よく混乱するので，自分用のメモとして分かりやすくまとめておく．

遅延伝播*1についての説明は省略．

要件

半群 $(S, \bullet)$，モノイド $(O, \circ, e)$ と，(外部) 二項演算 $\triangleleft : S \rightarrow O \rightarrow S$ について，

$\forall s \in S. \ s \triangleleft e = s$
$\forall s \in S. \ \forall p, q \in O. \ s \triangleleft (p \circ q) = (s \triangleleft p) \triangleleft q$
$\forall s, t \in S. \ \forall p \in O. \ (s \bullet t) \triangleleft p = (s \triangleleft p) \bullet (t \triangleleft p)$

を満足すればよい．

$S$ は (連続) 部分列の畳み込み, $O$ と $\triangleleft$ は部分列に対する一様な作用を表現する．

具体例

区間最小値 & 区間加算

$(S, \bullet) := (\mathbb{R}, \min)$
$(O, \circ, e) := (\mathbb{R}, +, 0)$
$\triangleleft := +$

type S = Double
type O = Double

opS :: S -> S -> S
opS = min

opO :: O -> O -> O
opO = (+)

act :: S -> O -> S
act = (+)

要件を確認する．

$(\mathbb{R}, \min)$ は半群の要件を満たす．
$(\mathbb{R}, +, 0)$ はモノイドの要件を満たす．
$\forall s \in \mathbb{R}. \ s + 0 = s$
$\forall s \in \mathbb{R}. \ \forall p, q \in \mathbb{R}. \ s + (p + q) = (s + p) + q$
$\forall s, t \in \mathbb{R}. \ \forall p \in \mathbb{R}. \ \min(s, t) + p = \min(s + p, t + p)$

区間和 & 区間加算

作用が分配的でないときは，区間の長さを持つ必要がある．

$S := \mathbb{R} \times \mathbb{N}$
$\forall (l, n), (r, m) \in S. \ (l, n) \bullet (r, m) := (l + r, n + m)$
$(O, \circ, e) := (\mathbb{R}, +, 0)$
$\forall (s, n) \in S. \ \forall p \in O. \ (s, n) \triangleleft p := (s + np, n)$

type S = (Double, Int)
type O = Double

opS :: S -> S -> S
(l, n) `opS` (r, m) = (l + r, n + m)

opO :: O -> O -> O
opO = (+)

act :: S -> O -> S
(s, n) `act` p = (s + fromIntegral n * p, n)

要件を確認する.

$(\mathbb{R} \times \mathbb{N}, \bullet)$ は半群の要件を満たす ($\because$ 半群 $(\mathbb{R}, +)$, $(\mathbb{N}, +)$ の直積)．
$(\mathbb{R}, +, 0)$ はモノイドの要件を満たす．
$\forall (s, n) \in \mathbb{R} \times \mathbb{N}.$
- $(s + n \times 0, n) = (s, n)$
$\forall (s, n) \in \mathbb{R} \times \mathbb{N}. \ \forall p, q \in \mathbb{R}.$
- $(s + n(p + q), n) = ((s + np) + nq, n)$
$\forall (s, n), (t, m) \in \mathbb{R} \times \mathbb{N}. \ \forall p \in \mathbb{R}.$
- $((s + t) + (n + m)p, n + m) = ((s + np) + (t + mp), n + m)$

区間和 & 区間代入

代入は右零半群で表現できる．これに単位元を添加しモノイドに拡張する．

$S := \mathbb{R} \times \mathbb{N}$
$\forall (l, n), (r, m) \in S. \ (l, n) \bullet (r, m) := (l + r, n + m)$
適当な $e \notin \mathbb{R}$ を取って，
- $O := \mathbb{R} \cup \{e\}$
- $\forall l, r \in O. \ l \circ r := \begin{cases} l & (r = e) \\ r & (\text{otherwise}) \end{cases}$
$\forall (s, n) \in S. \ \forall p \in O.$
- $(s, n) \triangleleft p := \begin{cases} (s, n) & (p = e) \\ (np, n) & (\text{otherwise}) \end{cases}$

type S = (Double, Int)
type O = Maybe Double

opS :: S -> S -> S
(l, n) `opS` (r, m) = (l + r, n + m)

opO :: O -> O -> O
l `opO` Nothing = l
_ `opO` r = r

act :: S -> O -> S
(s, n) `act` Nothing = (s, n)
(_, n) `act` (Just p) = (fromIntegral n * p, n)

これは要件を満たす．証明は省略．

参考

*1:遅延評価とも呼ばれる．遅延セグメント木などを参照のこと．

kuretchi's blog

競技プログラミングなどなど...

"遅延伝播" の一般化

要件

具体例

区間最小値 & 区間加算

区間和 & 区間加算

区間和 & 区間代入

参考