noshi91のメモ

データ構造のある風景

Aliens DP で辺の本数が区間で指定される場合

概要

https://dic.kimiyuki.net/d-edge-shortest-path-monge

この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 a 本以上  b 本以下使う最短路」も同じように解くことができることを解説します。

本文

合成積

関数  f _ 1, f _ 2: \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace の合成積  f _ 1 \square f _ 2 は \begin{align} (f _ 1 \square f _ 2)(x) &= \inf _ {x _ 1 + x _ 2 = x} (f _ 1(x _ 1) + f _ 2(x _ 2)) \end{align} で定義されます。  f _ 1, f _ 2 が凸で  f _ 1 \square f _ 2 - \infty にならなければ、 f _ 1 \square f _ 2 は凸です。

凸共役関数

関数  f: \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace, ~ ~ \exists x. ~ f(x) \neq + \infty に対して、その凸共役関数  f ^\bullet: \mathbb{R} \mapsto \mathbb{R} \cup \lbrace +\infty \rbrace を \begin{align} f ^\bullet (p) &= \sup _ x (px - f(x)) \end{align} で定義します。 本記事では  \displaystyle f ^ \bullet (p) = - \min _ x (f(x) - px) と思っても差し支えありません。 凸共役関数は本来もっと広いクラスの関数に対して定義されますが、本記事ではこれで十分です。

凸共役関数に対していくつかの良い性質が成り立ちます。

  •  f ^ \bullet は凸関数
  •  f が凸で特定の条件を満たすと  f ^ {\bullet \bullet} = f
  •  f _ 1, f _ 2 が凸で特定の条件を満たすと  (f _ 1 \square f _ 2) ^ \bullet = f _ 1 ^ \bullet + f _ 2 ^ \bullet

これらの条件は少し複雑なので、本記事では特に確認せずに使用します。 [1] などを確認してください。

問題の整理

 f(x) を、辺を  x 本使うという条件下での最短距離と定義します。 すると、

  •  f は凸
  • 任意の  p に対し、 \displaystyle \min _ x (f(x) - px) = - f ^ \bullet (p) が高速に評価できる
  •  f(d) を求めよ

という問題であると整理できます。

 f(d) の求め方

\begin{align} f(d) &= f ^ {\bullet \bullet} (d) \cr &= - \min _ {p} (f ^ \bullet (p) - dp) \cr \end{align}

 f ^ \bullet は凸なので  p \mapsto f ^ \bullet (p) - dp も凸であり、その最小化は三分探索で行えます。  f ^ \bullet (p) が高速に評価できるので、目的が達成されました。

 \displaystyle \min _ {a \leq x \leq b} f(x) の求め方

 \delta _ {\lbrack a , b \rbrack}: \mathbb{R} \to \mathbb{R} \cup \lbrace +\infty \rbrace を \begin{align} \delta _ {\lbrack a , b \rbrack} (x) &= \begin{cases} 0 & \quad (a \leq x \leq b) \cr +\infty & \quad (\text{otherwise}) \end{cases} \end{align} で定義します。このとき \begin{align} \min _ {a \leq x \leq b} f(x) &= (f \square \delta _ {\lbrack -b , -a \rbrack}) (0) \cr &= (f \square \delta _ {\lbrack -b , -a \rbrack}) ^ {\bullet \bullet} (0) \cr &= - \min _ {p} ((f \square \delta _ {\lbrack -b , -a \rbrack}) ^ \bullet (p) - 0p) \cr &= - \min _ {p} (f ^ \bullet + {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet) (p) \end{align}  f ^ \bullet, \delta _ {\lbrack -b , -a \rbrack} ^ \bullet は凸関数なのでその和も凸であり、その最小化は三分探索で行えます。  {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet は非常に単純な形になるので高速に評価でき、目的が達成されます。実際、 \begin{align} {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet (p) &= \begin{cases} -bp &\quad (p \leq 0) \cr -ap &\quad (p \geq 0) \end{cases} \end{align} です。

参考文献

[1] 室田一雄. (2001). 離散凸解析. 共立出版株式会社.

Top Tree の構造の変種

注意: 雑です

概要

[1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思いついたので、本記事で説明します。

本文

link cut tree に類似した構造になっていて、根付き木を管理します。 各辺は solid と dashed の 2 状態のいずれかであり、各頂点について子とをつなぐ辺の内 solid なものは高々  1 本とするのも link cut tree と同様です。

link cut tree と異なるところは

  • solid edge からなるパス  P を管理する二分探索木  \mathcal{C}
    • link cut tree:  P を頂点の列と見て、 P の頂点が  \mathcal{C} の頂点と  1 1 対応する。
    • 提案手法:  P を頂点と辺の列と見て、 P の頂点が  \mathcal{C} の葉に、 P の辺が  \mathcal{C} の内部ノードに  1 1 対応する。
  • 頂点  v に連なる dashed edge の管理
    • link cut tree: それぞれの dashed edge から  v (に対応する  \mathcal{C} の頂点) へポインタを張る。
    • 提案手法: 二分探索木  \mathcal{R} で dashed edge を管理する。各 dashed edge と  \mathcal{R} の頂点が  1 1 対応する。 \mathcal{R} の頂点は middle child として dashed edge の先の部分木を管理する木構造の根へポインタを張る。

具体例です。

f:id:noshi91:20220102003524j:plain

図 1: 管理したい根付き木(左)と対応する link cut tree の例(右)。頂点の数字は元の木の頂点と対応している。

f:id:noshi91:20220102003753j:plain

図 2: 管理したい根付き木(左)と対応する提案手法の木の例(右)。丸いノードは元の木の頂点と、四角いノードは元の木の辺と対応している。

管理したい根付き木を  T = (V, E) とすれば、データ構造の全ての頂点が  V \amalg E と完全に  1 1 対応します。 また、提案した構造でも link cut tree と同様に splay や expose を行えば時間計算量が  \text{amortized} ~ \mathrm{O}(\log(N)) になることも証明したつもりになっています (少し自信がありません)。

参考文献

[1] Alstrup, S., Holm, J., Lichtenberg, K. D., & Thorup, M. (2005). Maintaining information in fully dynamic trees with top trees. Acm Transactions on Algorithms (talg), 1(2), 243-264.

[2] Tarjan, R. E., & Werneck, R. F. F. (2005, January). Self-adjusting top trees. In SODA (Vol. 5, pp. 813-822).

容量下限などが付いている最小費用流

概要

辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。

記法の定義

 G = (V, E) を有向グラフとします。 フロー  \xi \in \mathbb{Z} ^ E に対して、その境界  \partial \xi \in \mathbb{Z} ^ V \displaystyle \partial \xi _ v = \sum _ {(v, u) \in E} \xi _ u - \sum _ {(u, v) \in E} \xi _ u で定義します。 つまり、境界は各頂点から流れ出る量を表しています。

ベクトルに対して不等号を使ったときは、全ての成分について同時にその不等号が成り立つものと解釈します。例:  0 \leq c \Leftrightarrow c は非負ベクトル

 \lVert \cdot \rVert _ 1 L ^ 1 ノルムで、成分毎の絶対値の和です。

基本的な最小費用流

  • 枝コスト  \gamma \in \mathbb{Z} _ {\geq 0} ^ {E}
  • 容量上限  \overline{c} \in \mathbb{Z} ^ {E}
  • source  s \in V
  • sink  t \in V
  • 流量  f \in \mathbb{Z} _ {\geq 0}
  •  s \neq t

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi _ v = \begin{cases} f &\quad (v = s) \cr -f &\quad (v = t) \cr 0 &\quad (\text{otherwise}) \end{cases} \end{align}

 0 \leq \overline{c} の場合 ACL を使うとそのまま解くことができます。  0 \leq \overline{c} でない場合は解がありません。 時間計算量は  \mathrm{O}(f (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert)) です。

b-flow

  • 枝コスト  \gamma \in \mathbb{Z} _ {\geq 0} ^ {E}
  • 容量上限  \overline{c} \in \mathbb{Z} ^ {E}
  • 供給  x \in \mathbb{Z} ^ {V}

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad 0 \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

 \displaystyle \sum _ {x _ v \gt 0} x _ v = - \sum _ {x _ v \lt 0} x _ v が成り立っていないときは解がありません。 そうでないとき

  1. 超頂点  s, t を作成する
  2.  x _ v \gt 0 である  v に対して、 s から  v に容量上限  x _ v コスト  0 の辺を張る
  3.  x _ v \lt 0 である  v に対して、 v から  t に容量上限  - x _ v コスト  0 の辺を張る
  4.  s から  t \lVert x \rVert _ 1 / 2 流す

で前述の問題に帰着されます。 時間計算量は  \mathrm{O}(\lVert x \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) ) です。

容量下限付き

  • 枝コスト  \gamma \in \mathbb{Z} _ {\geq 0} ^ {E}
  • 容量下限  \underline{c} \in \mathbb{Z} ^ {E}
  • 容量上限  \overline{c} \in \mathbb{Z} ^ {E}
  • 供給  x \in \mathbb{Z} ^ {V}

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

これは

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} (\xi - \underline{c}) + \gamma ^ {\top} \underline{c} \cr \text{subject to}&\quad 0 \leq \xi - \underline{c} \leq \overline{c} - \underline{c} \cr &\quad \partial (\xi - \underline{c}) = x - \partial \underline{c} \end{align}

と書き換えることができます。 したがって  \xi - \underline{c} をフローと思うことで前述の問題に帰着されます。 時間計算量は  \mathrm{O}(\lVert x - \partial \underline{c} \rVert _ 1 (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert)) \subseteq \mathrm{O}( (\lVert x \rVert _ 1 + \lVert \underline{c} \rVert _ 1) (\lvert V \rvert + \lvert E \rvert) \log (\lvert V \rvert + \lvert E \rvert) ) です。

枝コストが負

  • 枝コスト  \gamma \in \mathbb{Z} ^ {E}
  • 容量下限  \underline{c} \in \mathbb{Z} ^ {E}
  • 容量上限  \overline{c} \in \mathbb{Z} ^ {E}
  • 供給  x \in \mathbb{Z} ^ {V}

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \partial \xi = x \end{align}

 \gamma _ a \lt 0 である全ての  a \in E について、

  •  a の向きを逆にする
  •  \gamma _ a \leftarrow - \gamma _ a
  •  (\underline{c} _ a, \overline{c} _ a) \leftarrow (-\overline{c} _ a, -\underline{c} _ a)

とすると、前述の問題に帰着されます。 時間計算量はコストが負の辺の容量上限で変わるので、適宜計算してください。

供給が区間、境界に線形のコスト

  • 枝コスト  \gamma \in \mathbb{Z} ^ {E}
  • 容量下限  \underline{c} \in \mathbb{Z} ^ {E}
  • 容量上限  \overline{c} \in \mathbb{Z} ^ {E}
  • 境界コスト  \zeta \in \mathbb{Z} ^ V
  • 供給下限  \underline{x} \in \mathbb{Z} ^ {V}
  • 供給上限  \overline{x} \in \mathbb{Z} ^ {V}

\begin{align} \text{Minimize}&\quad \gamma ^ {\top} \xi + \zeta ^ {\top} \partial \xi \cr \text{subject to}&\quad \underline{c} \leq \xi \leq \overline{c} \cr &\quad \underline{x} \leq \partial \xi \leq \overline{x} \end{align}

  1. 超頂点  s を作成する
  2.  v \in V について、 s から  v に容量下限  \underline{x} _ v 容量上限  \overline{x} _ v コスト  \zeta _ v の辺を張る
  3. 供給  x = 0 として前述の問題に帰着

その他

 \mathbb{Z} の場合で議論しましたが、コストが  \mathbb{R} の場合や、 \pm \infty が含まれる場合も概ね同様に議論できます。 ただし容量下限付きを下限  0 に帰着するときに下限  \underline{c} - \infty が含まれていると壊れます。 これは容量上限  + \infty でコストが負の辺に対して「あらかじめ限界まで流しておく」が使えないことと同じです。

流量  f が指定されず自由な量流していい最小費用流は、供給が区間の場合を使えば定式化できます。

カタラン数を鏡像法で理解する

概要

この記事の内容は [1] の解説の一部を抜き出して説明したものです。 カタラン数  C(N) \displaystyle \binom{2N}{N} - \binom{2N}{N - 1} と等しいことを、鏡像法 *1 で説明します。

本文

 C(N) は、グリッド上を右上方向に、 (0, 0) から  (N, N) まで、 x \geq y を満たすように移動する方法の数と一致します。

f:id:noshi91:20210710163922j:plain

 x \geq y の条件を一旦忘れて、 (0, 0) から  (N, N) までの経路の本数を数えることを考えます。 これは以下のような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164327j:plain

 x \geq y を、 x + 1 = y を通らない、と言い換えます。 するとカタラン数は、先ほどの例において  x + 1 = y 上で  \mathrm{dp} = 0 にするような動的計画法で計算できます。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr 0 &\quad ( i + 1 = j ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710164812j:plain

この  x + 1 = y 上で  \mathrm{dp} = 0 にする操作を陽に行わずに表現する方法として、 x + 1 = y に対して  (0, 0) と対称な位置に  -1 の重みをもつスタート地点を置くという方法があります。

\begin{align} \mathrm{dp}(i, j) = \begin{cases} 1 &\quad ( (i, j) = (0, 0) ) \cr -1 &\quad ( (i, j) = (-1, 1) ) \cr \mathrm{dp}(i - 1, j) + \mathrm{dp}(i, j - 1) &\quad (\mathrm{otherwise}) \end{cases} \end{align}

f:id:noshi91:20210710170014j:plain

対称性から、対称軸上では  \mathrm{dp} = 0 となることが分かるので、普通の経路数の動的計画法の更新式で、上手くカタラン数が求まっています。 一方で  (0, 0) を始点とする経路の数と  (-1, 1) を始点とする経路の数は独立ですから、単に足し合わせれば

\begin{align} \text{カタラン数} &= \lbrace (0, 0) \text{から} (N, N) \text{への経路の数} \rbrace + (-1) \cdot \lbrace (-1, 1) \text{から} (N, N) \text{への経路の数} \rbrace \cr C(N) &= \binom{2N}{N} - \binom{2N}{N-1} \end{align}

が従います。

参考文献

  • [1]

    ネタバレ注意

    yukicoder 1241 Eternal Tours

*1:鏡像法は物理学の用語のようですが、発想が非常に似ているので、名前を借りています。

最小カット問題の k 値への一般化

概要

最小カットを用いると、 \alpha \in \mathbb{R},\ \theta _ i : \lbrace 0, 1 \rbrace \to \mathbb{R} 及び劣モジュラな  \phi _ {i, j} : \lbrace 0, 1 \rbrace ^ 2 \to \mathbb{R} について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{align}

という問題が解けます。[2]

これを一般化して、 \alpha \in \mathbb{R},\ \theta _ i : k \to \mathbb{R} 及び Monge な  \phi _ {i, j} : k ^ 2 \to \mathbb{R} について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in k ^ n \end{align}

は最小カットを用いて解けます。

本記事は [1] の内容を定式化し、表現可能な条件を明示的に記述します。

グラフの作り方

各変数  x _ i に対して、 \lbrace 0, 1 \rbrace の値を取る  k - 1 個の変数  \lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1} を作ります。 さらに、 x _ i ^ d = 1 \land x _ i ^ {d + 1} = 0 の場合  + \infty のコストが掛かることにします。 これにより  \lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1} は丁度  k 種類の状態を取るようになり、 x _ i ^ d = 1 \leftrightarrow x _ i \lt d と対応させられます。

 \theta _ i : k \to \mathbb{R} が表現可能なことを示します。  x _ i ^ d に対する  1 変数関数は常に表現可能であったことを思い出し、 x _ i ^ d = 1 のとき  \theta _ i (d - 1) - \theta _ i (d) のコストを掛けます。 さらに無条件で  \theta _ i (k - 1) のコストを掛けると、 \theta _ i が表現されます。

下図は上述の方法で表現した後、さらにグラフでの表現に直したものです。

f:id:noshi91:20210629043614j:plain

 \phi _ {i, j} : k ^ 2 \to \mathbb{R} が Monge ならば表現可能なことを示します。  \alpha \theta _ i, \theta _ j を使うことで、 \phi _ {i, j} (0, d) = \phi _ {i, j} (d, 0) = 0 \ (\forall \ d) としてよいです。  x _ i ^ d = x _ j ^ e = 0 のとき  \phi _ {i, j} (d, e) - \phi _ {i, j} (d, e - 1) - \phi _ {i, j} (d - 1, e) + \phi _ {i, j} (d - 1, e - 1) のコストを掛けます。  \phi _ {i, j} の Monge 性から、このコストは劣モジュラです。

yukicoder No.119 旅行ツアーの問題

この節は [3] の内容を前節の内容を通して捉え直します。

各国  i について  0: 国に行かない,  1: 国には行くがツアーに行かない,  2: ツアーに行く, の  3 つの選択肢を選ぶ問題であり、 k = 3 とした場合の前節の問題の枠組みで解釈できます。  B _ i, C _ i に関係する部分は  1 変数関数になるため、常に表現可能です ( B _ i, C _ i が負であっても)。  2 変数が関係する部分は、「国  i のツアーに行き国  j に行くならば、国  j のツアーに行かなければならない」です。 これを図示すると以下のようなコストになります。

f:id:noshi91:20210629043658j:plain

このままでは Monge でないので、 0, 1, 2 1, 0, 2 の順に並び替えます。すると以下のようになります。

f:id:noshi91:20210629043940j:plain

これは Monge なので、最小カットで解くことができます。  k = 2 の場合  0, 1 を全ての変数で一斉に入れ替えても劣モジュラ性は変化しませんでしたが、 k \geq 3 の場合は Monge 性に影響を与えるということになります。

問題例

出題場所 コンテスト名 問題名
0
KUPC
KUPC2019
123パズル
1
ARC
ARC 107
Sum of Abs

その他

  • グラフの作り方から明らかなように、 k の値は変数ごとに異なっても構いません。

参考文献

3 次元空間のクエリを処理する Wavelet Matrix

概要

Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。 これを発展させて 3 次元空間の点群に関するクエリを  \Theta ( ( \log ( \sigma ) ) ^ 2 ) で処理するデータ構造が存在します。

出来ること

  •  \mathtt { new } ( A )
    •  A を非負整数の  2 つ組の列として、データ構造を構築する。
    • 時間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 )
    • 空間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 / w )
    •  \sigma は各成分の最大値
  •  \mathtt { count } ( l , r , d , u , s , t )
    •  A \lbrack l , r ) で第  0 成分が  \lbrack d , u ) かつ第  1 成分が  \lbrack s , t ) のものの個数を出力する。
    • 時間計算量  \Theta ( ( \log ( \sigma ) ) ^ 2 )
  •  \mathtt { quantile } ( l , r , d , u , k )
    •  A \lbrack l , r ) で第  0 成分が  \lbrack d , u ) のもののうち、第  1 成分が  k 番目に小さいものを出力する。
    • 時間計算量  \Theta ( ( \log ( \sigma ) ) ^ 2 )

アルゴリズム

通常の Wavelet Matrix における  \mathtt { quantile } ( l , r , k ) の処理は以下のような具合でした。

int ret = 0;
for (int p = matrix.size(); p-- != 0;) {
    bit_vector &vec = matrix[p];
    int zeros = vec.rank0(l, r); // この段の [l, r) における 0 の個数
    if (zeros <= k) { // 答えの p bit 目は 1
        ret |= 1 << p;
        k -= zeros;
        l = vec.rank0(0, n) + vec.rank1(0, l);
        r = vec.rank0(0, n) + vec.rank1(0, r);
    } else {
        l = vec.rank0(0, l);
        r = vec.rank0(0, r);
    }
}
return ret;

 1 成分についての Wavelet Matrix を構築して、 \mathtt { quantile } ( l , r , d , u , k ) のクエリを処理することを考えます。  \mathtt { quantile } ( l , r , k ) と異なるのは、zeros を計算する部分のみです。 この部分を、第  0 成分が  \lbrack d , u ) の要素に限定して数えることが出来れば、全く同様の処理を行うことが出来ます。 格段について、bitvector が 0 の成分だけ抜き出して第  0 成分についての Wavelet Matrix を構築すれば、求める値を計算することが可能です。

 \mathtt { count } ( l , r , d , u , s , t ) もほとんど同様です: 第  1 成分について通常の処理をしながら、答えに加算する時だけ第  0 成分を考慮した値を足し上げます。

実装例

Submission #23120967 - AtCoder Beginner Contest 203(Sponsored by Panasonic)

ABC203 D - Pond に提出して TLE したものです。

区間を 2 次元平面にプロットする

概要

区間  \lbrack l , r ) l, r のそれぞれを軸とする  2 次元平面にプロットするという方法を紹介します。

f:id:noshi91:20210505141442j:plain:w500

まず、 1 つの区間を置いた図がこれです。 赤い点がプロットされた区間であり、斜めの対角線を  \lbrack 0 , n ) と思うと  \lbrace で示した部分がその区間に該当します。 点線によって領域が  6 つに分けられており、区間と他の区間との位置関係が  6 通りあることがすぐに分かります。 別の区間 (青) を置いてみると以下のようになります。

f:id:noshi91:20210505142051j:plain:w500

この場合、青の区間と赤の区間は overlap しており、青が左側にあります。 他の領域はそれぞれ包含や非交に対応しています。 この図示によって、例えば  2 つの区間の位置関係を判定したいときにどのような条件式を書けばよいかなどを素早く確実に導出することができます。 また、区間が関わる動的計画法などのイメージにも便利です。*1

*1:効果には個人差があります