# ITソリューション室 AdventCalender2024 Day22
## はじめに
はじめまして，ei1906です．外部向けにはNASSUNとか名乗っておけばいいですかね（外部公開する気はなかったんですが）．
本文章はITソルーション室 Advent Calendar 2024のために書き下ろされたものです．22日目の投稿になります．ここまで濃厚な記事ばかりで，おじさんになった私は美味しくSUSUれておらず，胃もたれをしながら文章を書いています．卓上調味料は辛うじて倒していません．
さて，ITソルーション室の皆さんはご存知の通り，私は開発ゴリゴリ人間ではないので開発の話はできません．幸いなことに（？）競技プログラミングをたまにやっているので，アルゴリズムやデータ構造の話を記そうと思います．誤ったことを書いていたらごめんなさい．
本記事は，力尽きていなければ以下の豪華2部構成でいこうと思います．
**・What is SegmentTree
・DPのかほりとは**
時間があるときに読むことを推奨します．以下本編

---
## What is SegmentTree
競技プログラミングでは，**セグメントツリー**というデータ構造が（体感）頻繁に登場します．セグメントツリーとは，数列の区間に対しての演算が高速で行える木構造のことを指します．より詳細には，セグメントツリーは完全二分木となっています．ここでの演算とは，大きく分けて以下の2つを指します．
- **更新処理**：ある区間に対して加減算などを行い，値を更新する処理
- **クエリ処理**：ある区間の総和や最大値最小値を求める処理

例えば，数列$\{1, 2, 3, 4, 5, 6\}$があったとします．このうち，区間$[2, 5]$に$10$を加算したい，すなわち数列を$\{1, 12, 13, 14, 15, 6\}$の形にしたいとしましょう．愚直的な方法であれば反復処理を用いて

for (int i = 2;i <= 5;i ++) {
    array[i] += 10;
}

のように記述するはずです（配列は0-indexedだろ！というツッコミは無視）．この場合，数列の長さを$N$とすると，$O(N)$となります（計算量については[ここ](https://atcoder.jp/contests/apg4b/tasks/APG4b_w?lang=ja)を参照してください．誤解を恐れずにいうならば，おおよその処理回数みたいなものです）．一方，セグメントツリーであれば$O(log_2 N)$で更新処理を行うことができます（以降，$log_2 N$は$logN$と表記します）．こういった便利な部分があるわけです．

### 木構造とは
木構造はグラフの一種で，閉路を持たないグラフのことをいいます．グラフはノード（頂点）とエッジ（辺）からなるもので……説明が面倒になってきたので以下の図をご覧ください．
<center>
<img src="https://hackmd.io/_uploads/HJ3DRb2Xye.png" height=70% width=70%>
<br>
<b>図1</b>
</center>
<br>

図1における円が**ノード**，円と円を繋ぐ線が**エッジ**です．「閉路がない」とは「**ノードを辿っていったときに循環が生じていない**」だと思ってください．で，閉路がないと何が嬉しいのかというと，グラフで階層を表すことができるのが嬉しい点です．図1の木構造ならば，図2のように表現することができます（あくまで一例です）．
<center>
<img src="https://hackmd.io/_uploads/HJeo7zh7kg.png" height=70% width=70%>
<br>
<b>図2</b>
</center>

図2において赤で塗られたノードを**ルートノード**といいます．先ほどちゃっかり書いていた**階層**とは「各ノードにおいてルートノードからいくつのノードを辿るとたどり着けるか」だと思ってください．このように表現すると何が嬉しいのか（嬉しくないとこんな表現はしないのでね）というと，ノードのノードとの間に何らかの関係ができるのが嬉しいのです．閉路のあるグラフだと，辺でつながったノードsの関係は「つながっている」だけでした．どっちが強いとか，どっちが先にできたとかは実際に2つのノードを参照しないとわかりません．しかし，木構造であれば，そういった関係性をノードの構成で表すことができます（あくまでも何らかの法則に従って木構造が作られている場合ですが）．身近な例で説明すると，会社の権力関係（図3）では階層が上であるほど権力が強いといえます．他にも，家系図とかなら階層が上であるほど過去の人間であるといえますよね．
<center>
<img src="https://hackmd.io/_uploads/Sk2xNyWBJe.png" height=30% width=30%>
<br>
<b>図3</b>
</center>

### 本題：Segment Treeとは何か
本題です．まずは区間和をもつセグメントツリーの構造を図4に示します．データ数は$N = 8$で，数列は$A = \{1, 2, 3, 4, 5, 6, 7, 8\}$とします．
<center>
<img src="https://hackmd.io/_uploads/B1u2qJ-B1g.png" height=60% width=60%>
<br>
<b>図4</b>
</center>

数列$A$が末端のノード（葉ノードといいます）にあり，各ノードは子ノードの値を加算した値を持っていることがわかると思います．ルートノードは区間$[1, 8]$の総和を持っていますし，ルートノードの右側の子ノードは区間$[5, 8]$の総和を持っています．ゆえに，とある区間$[a, b]$の総和を求めたいときは適切なノードを参照すればいいので，計算量を減らすことができるというわけです．例えば，区間$[1, 5]$であれば区間$[1, 4]$の総和を持つノードと区間$[5, 5]$（書き方あってる？）の総和を持つノードを参照すればいいわけです．今見ているノードがどの区間の総和を持っているかは，再帰で辿っていればわかります．
言い忘れていましたが，セグメントツリーは完全二分木です．完全二分木とは葉ノードを除く全てのノードが2つの子ノードを持ち，かつ全ての葉ノードの階層が同一である木構造のことをいいます．だから各階層のノードは必ず$2^x(x > 0)$個となります．葉ノードには与えられた数列が入りますが，各階層のノードは$2^x$個なので，場合によっては少し水増しをします（例えば$N = 5$なら葉ノードの個数は$8$個必要なので，$N = 8$として水増しした部分は$0$で埋めるなどします，図5参照）．
<center>
<img src="https://hackmd.io/_uploads/Byhh4Wbrkg.png" height=60% width=60%>
<br>
<b>図5</b>
</center>

水増し後の葉ノードの数を$M$とすると，全体のノード数は$2M - 1$となります．最悪のケースは葉ノードを参照しなければならない場合なので，参照回数は$log(2M-1)$回となります．なんやかんやして総和算出の計算量は$O(logN)$ですね．
区間更新（今回だと区間加算）の場合は，更新したい葉ノードまで辿っていき，葉ノードを更新した後，途中で通ったノードの値を更新していけば整合性をとることができます．

#### 配列を用いた木構造の表現
普通，木構造はポインタを使って以下のように表現します．

typedef struct Node {
    int data;
    Node* leftNode;
    Node* rightNode;
};

このコードでは二分木を表現しているわけですが，他の木構造でも同様に，ノードで管理したいデータと子ノードへのポインタ（親ノードへのポインタをもつ場合もひょっとしたらあるかも）が一つのノードにおけるメンバ変数になるわけです．
一方，セグメントツリーでは違って，配列を用いた木構造の表現を行います．これは，セグメントツリーが完全二分木であり，データ数によってノードの数も決まる故に可能になっていると考えられます．図4のセグメントツリーを配列で表すと図6のようになります（配列名を`Seg`としています）．
<center>
<img src="https://hackmd.io/_uploads/HyCjKb-SJl.png" height=80% width=80%>
<br>
<b>図6</b>
</center>

配列で表現することで，あるノード$i$の子ノードを`Seg[i*2+1], Seg[i*2+2]`として参照することができます．親ノードであれば`Seg[(i-1)/2]`で参照できます．ただ，0-indexedなのか1-indexedなのかによっては少し変わるので注意してください．配列で表現することの利点は考えたことがなかったのですが，ポインタを使うときよりも木の構築が楽といった利点があるのかなと思います．葉ノードに数列をセットするときも，`Seg[N+i-2]`と参照していけば良いですからね（数列$A$を1-indexedとしているのでこうなっていますが，0-indexedなら`Seg[N+i-1]`のように参照することになります）．ただ，重ねて言いますが，セグメントツリーが完全二分木であるがゆえに配列で表現できるだけであるため，他の木構造でも必ず表現できるとはならないことを留意してください．

もっと詳しく知りたい！という方は[ここ](https://algo-logic.info/segment-tree/)を参照してください．実装例や遅延セグ木についても記載されています．

---
## 「DPのかほり」を探る
経験上，**DP**（**動的計画法**．ダイヤモンドパールではないです）は初心者にとって一つの壁であると思っています．なぜならば，他のアルゴリズムとは違い，決まった書き方のようなものがないからです．要するに，コピペして一部書き換えたらOK！とはならないので，正真正銘のアルゴリズム力が試されるという感じです．じゃあ一体どうすればDPが解けるのかというと，SZPPにいるつよつよerは「DPって感じがした」といいます．正直私も「問題を読んでてDPの匂いがした」って言っています．いい機会なので「DPの匂い」，いや，「DPのかほり」とは何なのかについて探ってみたいと思います．

以下，圧倒的主観です．

### そもそもDPとは何ぞや
そもそもDPとは何かをご存知でしょうか？自分は「過去に求めた値を用いて新しい値を求めること」と教わった記憶があります．例えば[フィボナッチ数列](https://terakoya.ameba.jp/a000001464/)とかがそうで，$i(i > 1)$番目のフィボナッチ数を$fib(i)$と表記すると，$fib(i) = fib(i-1)+fib(i-2)$として求められます．過去に$fib(i-1), fib(i-2)$を求めてあり，配列などにメモしてあるのならば「過去に求めた値を用いて新しい値を求める」と言ってもいいですよね．では，実際の定義はどうでしょうか．[Wikipedia](https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95)にはこう書かれていました．
> 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。

ほうほう．

> 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
>
> 1. 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
> 2. 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。

なるほど……わかりますか？わからないですよね．過去の自分は絶対に理解できません．
先ほどの定義を都合のいいように噛み砕くと，以下のようにできます．
- DPでは表（配列）を使う（次元数は問わない）
- 表のとある部分は，それよりも前に算出された部分によって求められる（例えば，`a[i][j]`は`a[i-1][j]`や`a[i][j-1]`などを使って導出できる）

つまり，DPで解く問題には表が必要不可欠だということです．表が必要だということは，インデックス$i, j$にあたるような何かが答えを求めるために必要だということです．ということは，「**答えを求めるために複数の指標（しかもそれぞれの指標は連続している）が必要となる**」ということが「DPのかほり」ではないでしょうか．

### 実際の問題を見てみる
実際の問題を見ながらDPの解き方を探ってみましょう．まずはこの問題，[EDPC-A Frog1](https://atcoder.jp/contests/dp/tasks/dp_a)です．
> $N$個の足場があります。足場には$1,2,…,N$と番号が振られています。各$i(1≤i≤N)$について、足場$i$の高さは$h_i$です。
> 最初、足場$1$にカエルがいます。カエルは次の行動を何回か繰り返し、足場$N$まで辿り着こうとしています。
> ・足場$i$にいるとき、足場$i+1$または$i+2$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$∣h_i−h_j∣$を支払う。
> カエルが足場$N$に辿り着くまでに支払うコストの総和の最小値を求めてください。

この問題で求めるのは「カエルが足場$N$に辿り着くまでに支払うコストの総和の最小値」です．このことから，答えの算出に必要なのは以下の2つだと考えることができます．
- どの足場を見ているかの指標$i(1 \leq i \leq N)$
- 足場$i$に辿り着くためにかかるコストの最小値

答えを求めるために連続値の指標$i$が絡むことから，この問題はDPで解くのではないかと感じます．DPで解くのでは？と思ったら，最初にDPテーブル（表のことです）の構造を考えましょう．今回の問題では指標が1つであるので，一次元配列で良さそうですね．ということで，DPテーブルは以下のようになります．
- $dp[i]:$ 足場$i$に辿り着くためにかかるコストの最小値

言い忘れていましたが，DPでは表の初期値を設定する必要があります．問題文に
> 最初、足場$1$にカエルがいます。

と書いてあるので，$dp[1] = h_1$と設定することができます．では，$dp[i]$はどのように設定できるでしょうか？問題文を読んでみると，
> ・足場$i$にいるとき、足場$i+1$または$i+2$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$∣h_i−h_j∣$を支払う。

と書いてありますね．つまり，$dp[i]$は以下のように設定できるようです．
- $dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))$

これを全ての$i(2 \leq i \leq N)$で求めていけば良さそうです．ただし，ここで注意すべきは$i = 2$のときです．$i - 2 = 0$なのですが，$dp[0]$は不定ですよね．ということで，$dp[2]$も予め設定しておきましょう（$dp[2] = dp[1]+abs(h[2]-h[1])$）．ということで，あとは実装すればこの問題が解けるはずです．

もう一問行ってみましょう．同じくEDPCから[EDPC-C Vavation](https://atcoder.jp/contests/dp/tasks/dp_c)です．問題は各自で読んでください．
読んだ前提で話を進めると，この問題で求めるのは「$N$日目に得られる幸福度の総和の最大値」だということがわかります．とりあえず，以下の2つは必要そうですよね．
- 何日目の幸福度を求めているかの指標$i(1 \leq i \leq N)$
- $i$日目に得られる幸福度の総和の最大値

連続値の指標$i$があるということで，この問題はDPで解けそうだということを感じ取ります．DPテーブルを考えると以下のようになるのではないでしょうか．
- $dp[i]:$ $i$日目に得られる幸福度の総和の最大値

あとはループを回してやれば……！と思えてきますが違います．釣られたなポッター．問題文をよく読んでみると，以下の文章が書かれています．

> 太郎君は飽き性なので、$2$日以上連続で同じ活動を行うことはできません。

つまり，前日にどの活動を行ったかについても保持しておく必要がある，ということです．要するに，指標「$i$日目にどの活動を行ったのか（活動A$:1$，活動B$:2$，活動C$:3$）」も必要だということです．
まとめます．この問題を解くために必要なのは以下の3つです．
- 何日目の幸福度を求めているかの指標$i(1 \leq i \leq N)$
- $i$日目に行った活動を示す指標$j(1 \leq j \leq 3)$
- $i$日目に活動$j$を行った場合得られる幸福度の総和の最大値

指標が2つあるので，DPテーブルは二次元となります．
- $dp[i][j]:$ $i$日目に活動$j$を行った場合得られる幸福度の総和の最大値

これさえわかれば，あとは実装するだけです．まずは初期値設定をします．
- $dp[1][1] = a_1$
- $dp[1][2] = b_1$
- $dp[1][3] = c_1$

$dp[0][1] = dp[0][2] = dp[0][3] = 0$としてもいいですね．初期値設定後は，$dp[i][j]$をどのように導出するかを考えます．今回の場合，$i$日目の幸福度の総和の最大値は$i-1$日目のものから計算できることがわかります．加えて，同じ活動を連続で行えないという制約から，$i$日目の幸福度は以下のように求めることがわかります．
- $dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a_i$
- $dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + b_i$
- $dp[i][3] = max(dp[i-1][1], dp[i-1][2]) + c_i$

最終的に，$max(dp[N][1], dp[N][2], dp[N][3])$が出力すべき答えとなります．

### 結論
ということで，「DPのかほり」＝「答えを求めるために，複数の，かつ連続した指標が必要となっている」なのではないかという仮説を立てました（別の室員は漸化式が思いつくかどうか，と言っていましたがそれもありですね）．が，結局のところ見極めるためには経験が必要だと思います．bit-DPや桁DPといった典型問題もありますし．なので，皆さんはたくさんDPを解いて慣れましょう．