yukicoder No.1117 数列分割 のセグメントツリーを用いた解法について

Question

前提・実現したいこと

yukicoder No.1117 数列分割 のセグメントツリーを用いた解法について、わからない箇所があり質問させていただきました。何かお分かりになられる方がいらっしゃいましたら、お助けいただけますと幸いです。

発生している問題

上記問題について、セグメントツリーを用いた解法があるようなのですが、セグメントツリーの更新について理解できていない箇所がございます。以下、上記コードからセグメントツリーの更新部分のみを抜粋したものとなります。

for (int j = 0; j < k; j++) {
        for (int i = n - 1; i >= 0; i--) {
            dp[j + 1][i + 1] = max(dp[j + 1][i + 1], seg1.get_query(i + 1 - m, i + 1) + sum[i + 1]);
            dp[j + 1][i + 1] = max(dp[j + 1][i + 1], seg2.get_query(i + 1 - m, i + 1) - sum[i + 1]);
            seg1.update_query(i + 1, dp[j + 1][i + 1] - sum[i + 1]);
            seg2.update_query(i + 1, dp[j + 1][i + 1] + sum[i + 1]);
        }
    }

提出者様の解説

自分が疑問に思っていることは、ある i についてセグメントツリーの i 番目の要素の更新が終わった後 i + 1 番目の要素を更新する際、今さっき更新した i 番目の要素も区間に含んでしまっているため正しく更新することができないのではないかということです。

自分の感覚としては、j ループ目の更新を行う際は、ある i について更新された後の dp の値をいったん別の配列等に保存し、すべての i について dp の値を求め終わった後、次の j + 1 ループに入る前にセグメントツリーの各要素を配列に一時保存した値に従って更新する、という方法でないと正しく動作しないのではないかと思ってしまいます。

セグメントツリーの更新を上記コードのようにしてしまっても問題ない理由について、何かお分かりの方がいらっしゃったらお助けいただけないでしょうか。

Answer 1

ある i についてセグメントツリーの i 番目の要素の更新が終わった後 i + 1 番目の要素を更新する際

iはデクリメントされてるのでi + 1番目の更新はi番目の更新の前に終わっています

Comments

[shukrin]

ご回答ありがとうございます。とても助かりました。以降はもっと注意深くコードを読むよう心がけようと思います。