分割統治法による区間の合計値の計算をしているコードでわからないところ

Question

前提

分割統治法による区間の合計値の計算をしているコードです。
なぜsolve(1,2)とsolve(2,3)は3＋１で足すのでしょうか
return s1 + s2;が使われているのでしょうか
しかし、コードを見る限り一番最後に合計を足すだけにreturn s1 + s2;が使われているようにしか見えません。
なぜ３＋１をするのかわかりますか

分割統治法による区間の合計値の計算をしているコード

#include <iostream>
using namespace std;

int N, A[109];

int solve(int l, int r) {
if (r - l == 1) return A[l];
int m = (l + r) / 2; // 区間 [l, r) の中央で分割する
int s1 = solve(l, m); // s1 は A[l]+...+A[m-1] の合計値となる
int s2 = solve(m, r); // s2 は A[m]+...+A[r-1] の合計値となる
return s1 + s2;
}

int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];

// 再帰呼び出し → 答えの出力
int Answer = solve(1, N + 1);
cout << Answer << endl;
return 0;
}

補足情報（FW/ツールのバージョンなど）

C++
ここにより詳細な情報を記載してください。

Comments

[ps_aux_grep]

3+1とは…？

[episteme]

配列の 前半部の総和 と 後半部の総和 を加えたら 配列全体の総和 が求まります。
それを再帰的にやってるんですけど...

[ALOHAMS]

入力値を追記していただけますか？

[jaogjig]

N＝4、a（3,1,4,1）です。

[episteme]

solve([3,1,4,1])
= solve([3,1]) + solve([4,1])
= ( solve([3]) + solve([1]) ) + ( solve([4]) + solve([1]) )
= ( 3 + 1 ) + ( 4 + 1 )
= 4 + 5
= 9

[jaogjig]

回答ありがとうございます。

Answer 1

前提

solve(int l, int r)関数は言ってしまえばデータの集合をトーナメント表式や決定木分類みたいに分割する処理を再帰的に行う関数です。
分かりやすい図を見つけたのでこちらのサイトを見てください。こちらはクイックソートの例ですが分ける部分の図示は全く同じです。
アルゴリズムとデータ構造④

中身の解説

では流れを見てみましょう。

int m = (l + r) / 2; // 区間 [l, r) の中央で分割する
int s1 = solve(l, m); // s1 は A[l]+...+A[m-1] の合計値となる
int s2 = solve(m, r); // s2 は A[m]+...+A[r-1] の合計値となる

ここがデータの分割の本筋です。データがまだ2個以上あるなら半分に分けるでという処理を行っています。この処理はそれだけです。
そして、データを半分に半分に…としていくと、最終的には１つになります。トーナメントも1:1ですよね。

if (r - l == 1) return A[l];

コード最初のこの一文は 「データが1個になったら中身教えろや！」っていう意味です。 ここでようやく最初の結果が返ってきます。(再帰処理の終端)
ここで終端の一つ手前に戻ってみると、

int s1 = solve(l, m); // 終端到達時はs1=A[l]
int s2 = solve(m, r); // 終端到達時はs2=A[m]
return s1 + s2;

1：1の隣り合うデータを合計して返してることがわかります。

そして、トーナメント表見ればわかることですが、この分割方法はダブりが発生しないので最終的に左半分データの合計＋右半分データの合計という形まで戻ってくることがわかります。

だから最終的にA[1]~A[N]までの総和が結果として帰ってくるのです。
3+1に関してはよくわかりませんが、ご自身でcinで1,3,1みたいに入力したからではないですか？

Comments

[jaogjig]

理解できました。（１、３）の関数で戻ってS2の方を処理することを抜け落ちていました。ありがとうございます。