配列 $a = (a_0, a_1, \dots, a_{n-1}) \in \Z^n$ に対して、次の種類のクエリを処理する問題を考えます。
- $\texttt{1}\; i\; x$
- $a_i \gets x$ で更新する
- $\texttt{2}\; l\; r$
- $(a_l, a_{l+1}, \dots, a_{r-1})$ の空でない連続部分列における、総和の最大値を求める
考察
意味論をイメージしながら納得するのは簡単ですが、数式としてちゃんと示したい気持ちになったので、そういう方針でやります。
区間和の最大値
2 つ目のクエリは、次のように記述できます。 $$ \max_{l\le i_l\lt i_r\le r} \sum_{j=i_l}^{i_r-1} a_j. $$ $r-l=1$ のとき、この値は $a_l$ に等しいです。 $r-l\ge 2$ のとき、$l\lt m\lt r$ なる $m$ を固定すると、次が成り立ちます。 $$ \begin{aligned} &\phantom{{}={}} \{(i_l, i_r) \mid l\le i_l\lt i_r\le r\} \\ &= \{(i_l, i_r) \mid l\le i_l\lt i_r\le m\} \\ & \qquad\quad {} \cup \{(i_l, i_r) \mid m\le i_l\lt i_r\le r\} \\ & \qquad\quad {} \cup \{(i_l, i_r) \mid l\le i_l\lt m\lt i_r\le r\}. \end{aligned} $$ よって、次のように分解できます。 $$ \begin{aligned} &\phantom{{}={}} \max_{l\le i_l\lt i_r\le r} \sum_{j=i_l}^{i_r-1} a_j \\ &= \max{\left\{\max_{l\le i_l\lt i_r\le m}\sum_{j=i_l}^{i_r-1} a_j, \max_{m\le i_l\lt i_r\le r}\sum_{j=i_l}^{i_r-1} a_j, \max_{l\le i_l\lt m\lt i_r\le r}\sum_{j=i_l}^{i_r-1} a_j\right\}}. \end{aligned} $$ 前者二つは、元の式の $(l, r)$ をそれぞれ $(l, m)$ と $(m, r)$ で置き換えた形になっています。後者についてさらに考えます。 $$ \begin{aligned} &\phantom{{}={}} \max_{l\le i_l\lt m\lt i_r\le r}\sum_{j=i_l}^{i_r-1} a_j \\ &= \max_{l\le i_l\lt m\lt i_r\le r} \left(\sum_{j=i_l}^{m-1} a_j + \sum_{j=m}^{i_r-1} a_j\right) \\ &= \left(\max_{l\le i_l\lt m} \sum_{j=i_l}^{m-1} a_j\right) + \left(\max_{m\lt i_r\le r}\sum_{j=m}^{i_r-1} a_j\right). \end{aligned} $$ これらは、それぞれ $(a_l, a_{l+1}, \dots, a_{m-1})$ の空でない接尾辞の総和の最大値と、$(a_m, a_{m+1}, \dots, a_{r-1})$ の空でない接頭辞の総和の最大値です。
接尾辞和の最大値
まず、$(a_l, a_{l+1}, \dots, a_{r-1})$ の空でない接尾辞の総和の最大値について考えます。
$r-l=1$ のときは $a_l$ に等しく、$r-l\ge 2$ のときは $l\lt m\lt r$ なる $m$ に対して $$ \{i \mid l\le i\lt r\} = \{i \mid l\le i\lt m\} \cup \{i \mid m\le i\lt r\} $$ が成り立つので、 $$ \begin{aligned} &\phantom{{}={}} \max_{l\le i\lt r} \sum_{j=i}^{r-1} a_j \\ &= \max{\left\{\max_{l\le i\lt m} \sum_{j=i}^{r-1} a_j, \max_{m\le i\lt r} \sum_{j=i}^{r-1} a_j\right\}} \end{aligned} $$ となります。後者は元の式の $(l, r)$ を $(m, r)$ に置き換えたものですが、前者についてはもう少し変形が必要です。 $$ \begin{aligned} &\phantom{{}={}} \max_{l\le i\lt m} \sum_{j=i}^{r-1} a_j \\ &= \max_{l\le i\lt m} \left(\sum_{j=i}^{m-1} a_j + \sum_{j=m}^{r-1} a_j\right) \\ &= \left(\max_{l\le i\lt m} \sum_{j=i}^{m-1} a_j\right) + \left(\max_{l\le i\lt m} \sum_{j=m}^{r-1} a_j\right) \\ &= \left(\max_{l\le i\lt m} \sum_{j=i}^{m-1} a_j\right) + \sum_{j=m}^{r-1} a_j \\ \end{aligned} $$ この 1 つ目の項は、元の式の $(l, r)$ を $(l, m)$ に置き換えたものであり、2 つ目の項は $(a_m, a_{m+1}, \dots, a_{r-1})$ の総和です。
接頭辞和の最大値
接尾辞の場合と同様にできます。
$r-l = 1$ のときは $a_l$ に等しく、$r-l\ge 2$ のときは $l\lt m\lt r$ なる $m$ に対して $$ \{i \mid l\lt i\le r\} = \{i \mid l\lt i\le m\} \cup \{i \mid m\lt i\le r\} $$ が成り立つので、 $$ \begin{aligned} &\phantom{{}={}} \max_{l\lt i\le r} \sum_{j=l}^{i-1} a_j \\ &= \max{\left\{\max_{l\lt i\le m} \sum_{j=l}^{i-1} a_j, \sum_{j=l}^{m-1} a_j + \left(\max_{m\lt i\le r} \sum_{j=m}^{i-1} a_j\right)\right\}} \end{aligned} $$ とできます。
二項演算の導入
ここまでで、「区間和の最大値」、「接尾辞和の最大値」、「接頭辞和の最大値」、「総和」がわかれば、それぞれを計算できることがわかりました。よって、$\Z^4$ 上での二項演算 $\circ$ を次のように定義します。 $$ \begin{aligned} &\phantom{{}={}} (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}) \circ (y_{\text{max-any}}, y_{\text{max-suffix}}, y_{\text{max-prefix}}, y_{\text{sum}}) \\ &= (\max{\{x_{\text{max-any}}, y_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}\}}, \\ & \qquad\quad \max{\{x_{\text{max-suffix}} + y_{\text{sum}}, y_{\text{max-suffix}}\}}, \\ & \qquad\quad \max{\{x_{\text{max-prefix}}, x_{\text{sum}} + y_{\text{max-prefix}}\}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}}). \end{aligned} $$
ここで、たとえば $(x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}) = (1, 10, 100, 1000)$ などに対応する数列は存在しませんが、一旦そうしたことは考えず、あくまで $\Z^4$ 上のそういう演算として考えることにします。それで不都合が生じたら、実際に対応する数列が存在するような $\Z^4$ の部分集合について考えることにします。
まず、これが半群をなすことを示します。すなわち、結合法則が成り立つことを示します。
Claim 1: 任意の $x, y, z \in \Z^4$ に対し、$(x\circ y)\circ z = x\circ(y\circ z)$ が成り立つ。
Proof
$$ \begin{aligned} &\phantom{{}={}} (x\circ y)\circ z \\ &= (\max{\{x_{\text{max-any}}, y_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}\}}, \\ & \qquad\quad \max{\{x_{\text{max-suffix}} + y_{\text{sum}}, y_{\text{max-suffix}}\}}, \\ & \qquad\quad \max{\{x_{\text{max-prefix}}, x_{\text{sum}} + y_{\text{max-prefix}}\}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}}) \circ (z_{\text{max-any}}, z_{\text{max-suffix}}, z_{\text{max-prefix}}, z_{\text{sum}}) \\ % &= (\max{\{\max{\{x_{\text{max-any}}, y_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}\}}, z_{\text{max-any}}, \max{\{x_{\text{max-suffix}} + y_{\text{sum}}, y_{\text{max-suffix}}\}} + z_{\text{max-prefix}} \}}, \\ &= (\max{\{\max{\{x_{\text{max-any}}, y_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}\}}, } \\ & \qquad\qquad\quad {z_{\text{max-any}}, \max{\{x_{\text{max-suffix}} + y_{\text{sum}}, y_{\text{max-suffix}}\}} + z_{\text{max-prefix}} \}}, \\ & \qquad\quad \max{\{ \max{\{x_{\text{max-suffix}} + y_{\text{sum}}, y_{\text{max-suffix}}\}}+z_{\text{sum}}, z_{\text{max-suffix}} \}}, \\ & \qquad\quad \max{\{ \max{\{x_{\text{max-prefix}}, x_{\text{sum}} + y_{\text{max-prefix}}\}}, x_{\text{sum}}+y_{\text{sum}} + z_{\text{prefix}} \}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}} + z_{\text{sum}}) \\ &= (\max{\{x_{\text{max-any}}, y_{\text{max-any}}, z_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}, } \\ & \qquad\qquad\quad {y_{\text{max-suffix}} + z_{\text{max-prefix}}, x_{\text{max-suffix}} + y_{\text{sum}} + z_{\text{max-prefix}} \}}, \\ & \qquad\quad \max{\{ x_{\text{max-suffix}} + y_{\text{sum}} + z_{\text{sum}}, y_{\text{max-suffix}} + z_{\text{sum}}, z_{\text{max-suffix}} \}}, \\ & \qquad\quad \max{\{ x_{\text{max-prefix}}, x_{\text{sum}} + y_{\text{max-prefix}}, x_{\text{sum}}+y_{\text{sum}} + z_{\text{prefix}} \}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}} + z_{\text{sum}}), \\ % --- &\phantom{{}={}} x\circ (y\circ z) \\ &= (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}) \circ {} \\ & \qquad\quad (\max{\{y_{\text{max-any}}, z_{\text{max-any}}, y_{\text{max-suffix}} + z_{\text{max-prefix}}\}}, \\ & \qquad\qquad\quad \max{\{y_{\text{max-suffix}} + z_{\text{sum}}, z_{\text{max-suffix}}\}}, \\ & \qquad\qquad\quad \max{\{y_{\text{max-prefix}}, y_{\text{sum}} + z_{\text{max-prefix}}\}}, \\ & \qquad\qquad\quad y_{\text{sum}} + z_{\text{sum}}) \\ &= (\max{\{x_{\text{max-any}}, \max{\{y_{\text{max-any}}, z_{\text{max-any}}, {y_{\text{max-suffix}} + z_{\text{max-prefix}}\}}, }} \\ & \qquad\qquad\quad {{x_{\text{max-suffix}} + \max{\{y_{\text{max-prefix}}, y_{\text{sum}} + z_{\text{max-prefix}}\}}}\}}, \\ & \qquad\quad \max{\{ x_{\text{max-suffix}} + y_{\text{sum}} + z_{\text{sum}}, \max{\{y_{\text{max-suffix}} + z_{\text{sum}}, z_{\text{max-suffix}}\}} \}}, \\ & \qquad\quad \max{\{ x_{\text{max-prefix}}, x_{\text{sum}} + \max{\{y_{\text{max-prefix}}, y_{\text{sum}} + z_{\text{max-prefix}}\}} \}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}} + z_{\text{sum}}) \\ &= (\max{\{x_{\text{max-any}}, y_{\text{max-any}}, z_{\text{max-any}}, x_{\text{max-suffix}} + y_{\text{max-prefix}}, } \\ & \qquad\qquad\quad {y_{\text{max-suffix}} + z_{\text{max-prefix}}, x_{\text{max-suffix}} + y_{\text{sum}} + z_{\text{max-prefix}} \}}, \\ & \qquad\quad \max{\{ x_{\text{max-suffix}} + y_{\text{sum}} + z_{\text{sum}}, y_{\text{max-suffix}} + z_{\text{sum}}, z_{\text{max-suffix}} \}}, \\ & \qquad\quad \max{\{ x_{\text{max-prefix}}, x_{\text{sum}} + y_{\text{max-prefix}}, x_{\text{sum}}+y_{\text{sum}} + z_{\text{prefix}} \}}, \\ & \qquad\quad x_{\text{sum}} + y_{\text{sum}} + z_{\text{sum}}). \quad\qed \end{aligned} $$
続いて、$\circ$ を $\Z^4$ から $(\Z\cup\{-\infty\})^4$ 上への演算に拡張するとモノイドになることを示します。結合法則は Claim 1 同様にして示すことができます。単位元の存在を示します。
Claim 2: $e = (-\infty, -\infty, -\infty, 0)$ とすると、任意の $x\in (\Z\cup\{-\infty\})^4$ に対して $x\circ e = e\circ x = x$ が成り立つ。
Proof
$$ \begin{aligned} &\phantom{{}={}} (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}) \circ (-\infty, -\infty, -\infty, 0) \\ &= (\max{\{x_{\text{max-any}}, -\infty, x_{\text{max-suffix}} + (-\infty)\}}, \\ & \qquad\quad \max{\{x_{\text{max-suffix}} + 0, (-\infty)\}}, \\ & \qquad\quad \max{\{x_{\text{max-prefix}}, x_{\text{sum}} + (-\infty)\}}, \\ & \qquad\quad x_{\text{sum}} + 0) \\ &= (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}), \\ % --- &\phantom{{}={}} (-\infty, -\infty, -\infty, 0) \circ (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}) \\ &= (\max{\{(-\infty), x_{\text{max-any}}, (-\infty) + x_{\text{max-prefix}}\}}, \\ & \qquad\quad \max{\{(-\infty) + x_{\text{sum}}, x_{\text{max-suffix}}\}}, \\ & \qquad\quad \max{\{(-\infty), 0 + x_{\text{max-prefix}}\}}, \\ & \qquad\quad 0 + x_{\text{sum}}) \\ &= (x_{\text{max-any}}, x_{\text{max-suffix}}, x_{\text{max-prefix}}, x_{\text{sum}}). \quad\qed \end{aligned} $$
数列中の各値 $a_i$ に対して、$(a_i, a_i, a_i, a_i) \in (\Z\cup\{-\infty\})^4$ を対応させればよいです。
使用例
あとがき
2019 年頃のえびちゃんが自力で思いつけたモノイドだったと思うので、印象深いものの一つです。当時から無限回既出ではあったと思います。
ところで、最近 Kadane’s algorithm の名前を聞く機会が減ったような気がします。
おわり
おわりです。
