冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 累積和と元データの変更—一点を書き換えたとき影響する保存値の範囲を追う|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

タイルの値を1枚だけ直した後、古い表の差が正しい区間とずれる区間を見分ける鍵は累積和です。

よくあるのは、タイルに書かれた値の区間合計を調べるため、高校生が先頭からの合計表を作った後、1枚の値の誤記に気づく場面です。元の値だけを直しても、すでに保存した合計表は自動では書き換わりません。それでも、古い表を使った答えがたまたま正しい区間があります。どの保存値が古いかと、どの区間の答えがずれるかは、分けて考える必要があります。

ここでは数値をすべて自作の条件とし、配列の1要素を1回だけ変更します。処理を複数回重ねた場合や、効率のよい更新方式の設計には広げず、変更前の表と変更後に作り直した表の関係を調べます。

要点(結論から)

  • A[t] を含み始めるのは P[t+1] です。
  • 変更量が 0 でなければ P[t+1] 以降が古くなります。
  • 変更箇所が区間内なら、新しい合計は古い差に変更量を加えた値です。

何を答える問題か

1つ目の型は、変更後も古い保存値のままでよい添字を選ぶ問題です。累積和の各値に変更箇所が含まれるかどうかを見ます。元配列の添字と累積和の添字は1ずれるので、その境目を先に書きます。

2つ目の型は、古い表の差を使っても変更後の区間合計が正しいかを判定する問題です。区間の外で変更した場合、左端より前で変更した場合と右端以降で変更した場合では、端点の保存値が古いかどうかは異なります。それでも差は一致します。

3つ目の型は、差がずれるときの大きさや向きを求める問題です。変更後の値から変更前の値を引いた量を使います。増えた場合と減った場合を同じ式で扱えますが、古い答えから新しい答えへ直すのか、その逆なのかを明記します。

区間は左端を含み右端を含まない半開区間とします。対象は添字が l 以上 r 未満の要素で、端点 l と r は 0 <= l <= r <= n を満たす整数です。l と r が等しければ空区間で、合計は 0 です。Pythonの添字は0から始まり、長さ n の配列の要素は 0 から n-1 までです。

保存値の境目を描く

元配列を A、変更前の累積和を P とします。P[0] は 0 で、P[k] は A の先頭から k 個の合計です。したがって、P[k] に含まれるのは添字 0 から k-1 までです。たとえば P[3] には A[2] が含まれますが、A[3] はまだ含まれません。

添字 t の値を old から new に変え、差を d = new − old とします。変更後の累積和を Q と書くと、k が t 以下なら P[k] に変更した要素は入らないため Q[k] = P[k] です。k が t より大きければ、その要素を1回含むため Q[k] = P[k] + d です。d が 0 でなければ P[t+1] から P[n] が変更後の値と食い違います。値を同じ値に書き直した場合は d が 0 なので食い違いません。

図1 変更した要素と累積和の境目を示す図

図1のように、A[t] を含み始める保存値は P[t] ではなく P[t+1] です。P[t] は変更箇所の直前までの合計です。この1つの違いが、古い値の範囲を判断する要になります。

変更後の区間合計は Q[r] − Q[l] です。古い表の差 P[r] − P[l] と比較すると、変更箇所 t が区間内、つまり l 以上 r 未満なら、右側の保存値だけに d が加わります。このとき新しい合計は古い差に d を加えた値です。

一方、t が l より小さい場合は、両端の保存値に同じ d が加わるため、引き算で相殺されます。t が r 以上の場合は、どちらの保存値にも d が加わりません。どちらも古い差は変更後の合計と一致します。左端と一致する t = l は区間内、右端と一致する t = r は区間外である点を特に区別してください。

基本例題:1枚の修正を表に移す

タイルの値を A = [2, 4, 1, 3] とします。先頭からの累積和を構築した後、添字 1 の値を 4 から 7 に直します。変更後の累積和を求め、古い表で区間 [1, 3) と [2, 4) の合計を計算した結果が正しいか答えてください。

次のプログラムは変更前に P を作り、A の1要素だけを変更し、その後 Q を作り直します。出力は最後の3行で、配列と2つの差を示します。i は現在足す要素の添字です。

A = [2, 4, 1, 3]
P = [0]
i = 0
while i < len(A):
    P.append(P[i] + A[i])
    i = i + 1
A[1] = 7
Q = [0]
i = 0
while i < len(A):
    Q.append(Q[i] + A[i])
    i = i + 1
print(P)
print(Q)
print(P[3] - P[1], P[4] - P[2])

まず変更前の構築を追います。各行の P は追加後の配列、i は末尾の加算後の値です。条件は各回の開始時に調べます。

判定時の i i < 4 追加する計算 追加後の P 更新後の i
0 真 0 + 2 = 2 [0, 2] 1
1 真 2 + 4 = 6 [0, 2, 6] 2
2 真 6 + 1 = 7 [0, 2, 6, 7] 3
3 真 7 + 3 = 10 [0, 2, 6, 7, 10] 4
4 偽 追加なし [0, 2, 6, 7, 10] 4

A[1] を 7 にすると A は [2, 7, 1, 3] です。P は変更前のままです。次に Q を [0]、i を 0 から開始します。

判定時の i i < 4 追加する計算 追加後の Q 更新後の i
0 真 0 + 2 = 2 [0, 2] 1
1 真 2 + 7 = 9 [0, 2, 9] 2
2 真 9 + 1 = 10 [0, 2, 9, 10] 3
3 真 10 + 3 = 13 [0, 2, 9, 10, 13] 4
4 偽 追加なし [0, 2, 9, 10, 13] 4

実行時の出力は次のとおりです。

[0, 2, 6, 7, 10]
[0, 2, 9, 10, 13]
5 4
図2 修正前後の累積和と区間の差の対応

図2のように、変更量は 7 − 4 = 3 です。P[0] と P[1] はそのまま、P[2] から P[4] はそれぞれ 3 小さい古い値です。区間 [1, 3) は添字 1 と 2 を含みます。古い差は 7 − 2 = 5、新しい合計は 7 + 1 = 8 です。変更箇所が左端にあり、古い答えは 3 小さくなります。

区間 [2, 4) は添字 2 と 3 を含み、変更箇所は左端より前です。古い差は 10 − 6 = 4、新しい差は 13 − 9 = 4 です。実際のタイルも 1 と 3 なので合計は 4 です。両端の保存値は古いものの、それぞれの不足分 3 が差で消えます。

標準例題:境界を一つずつ動かす

展示台の値を [3, 1, 5, 2, 4] とし、添字 3 の 2 を 6 に変更します。構築済みの P は [0, 3, 4, 9, 11, 15] です。変更後の Q と、[0, 3)、[3, 5)、[4, 5) の新しい合計を求め、古い差が正しいか判定してください。

変更量は 4 です。P[0] から P[3] はそのままで、P[4] と P[5] に 4 を加えると Q は [0, 3, 4, 9, 15, 19] になります。変更したのは添字 3 であり、P[3] は添字 2 までなので変わりません。

[0, 3) は右端が変更箇所と一致しますが、右端を含まないので対象は 3、1、5 です。古い差は 9、新しい合計も 9 です。[3, 5) は左端を含むので対象は 6、4 で、新しい合計は 10 です。古い差は 15 − 9 = 6 であり、変更量の 4 だけ小さくなります。[4, 5) は値 4 だけを含み、古い差も新しい差も 4 です。ここでは両端に変更量が加わります。

端点を数直線上の位置として扱うと、[0, 3) と [3, 5) はちょうど境界を共有します。添字 3 は後者に入り前者には入りません。両方に入れると二重に数え、どちらにも入れなければ数え落とします。区間の意味を決めてから式へ移すことが必要です。

発展例題:減少と空区間

番号札の値を [8, 5, 2] とします。添字 0 の 8 を 3 に変更しました。変更前の累積和は [0, 8, 13, 15] です。変更後の累積和、区間 [0, 2)、[1, 3)、[1, 1) の新しい合計と、古い差との差を求めてください。

変更量は 3 − 8 = -5 です。P[0] は変わらず、P[1] から P[3] に -5 を加えるので Q は [0, 3, 8, 10] です。[0, 2) の古い差は 13、新しい合計は 3 + 5 = 8 です。新しい値は古い差に -5 を加えたものです。減少でも式をそのまま使えます。

[1, 3) は 5 と 2 の合計 7 で、古い差 15 − 8 も 7 です。2つの保存値がともに 5 減ったので差は変わりません。[1, 1) は要素を含まず 0 です。同じ保存値を引くので、古い表でも新しい表でも 0 になります。空区間は変更箇所を含まないことを、端点の定義から判断できます。

値の変化が負なら、古い答えのほうが大きくなります。「古い表はいつも小さい」と覚えると、増加の例しか通りません。また、同じ値へ書き直す場合は d が 0 です。変更位置が区間に入っていても数値の差は生じず、保存値も実際には古くなりません。

誤答から境界を直す

基本例題で「添字 1 を直したから P[1] から全部に 3 を加える」と考えると、変更後の表を [0, 5, 9, 10, 13] としてしまいます。最初の食い違いは P[1] です。P[1] は先頭のタイル1枚、すなわち添字 0 の値だけを含みます。添字 1 は次の P[2] で初めて入ります。

図3 誤った更新開始位置と正しい境目の比較

図3のように、修正は P[2] から始めます。誤った表では [1, 3) の差が 10 − 5 = 5 となり、変更を含む区間なのに変化が消えてしまいます。正しくは 10 − 2 = 8 です。計算の最後ではなく、先に P[1] の意味を確認すると、誤りの発生箇所を特定できます。

もう一つの誤りは「古い保存値を使った差は必ず間違い」とすることです。基本例題の [2, 4) では両端が古く、両方の不足分が同じなので差は正しいままです。区間内に変更箇所があるかを先に判定し、区間外なら両端がともに影響を受けるか、ともに受けないかを確認します。保存値の正誤と差の正誤は別々の列に記すと混同を避けられます。

練習:先に5問を解く

以下の数値と場面はすべて自作です。各配列の添字は 0 からで、区間は左端を含み右端を含みません。累積和は変更前に作り、元配列の指定された1要素だけを変更します。

  1. 照明の値が [6, 2, 9] です。添字 2 を 9 から 4 に変更します。変更前後の累積和を配列で求め、値が食い違う保存値の添字を答えてください。
  2. 棚の値が [1, 7, 3, 6] です。添字 1 を 7 から 10 に変更します。区間 [2, 4) の古い差と新しい合計を整数で求め、両者が一致する理由を答えてください。
  3. カードの値が [4, 8, 2, 5] です。添字 2 を 2 から 6 に変更します。[0, 2) と [2, 4) について、古い差と新しい合計をそれぞれ整数で答えてください。
  4. 小箱の値が [7] です。添字 0 を 7 から 1 に変更します。[0, 1) と空区間 [1, 1) の古い差と新しい合計をそれぞれ求めてください。
  5. 盤の値が [5, 3, 8] です。添字 1 を同じ 3 に書き直します。変更前後の累積和と [1, 3) の合計を答え、食い違う保存値があるか判定してください。

練習の答えと照合

  1. 変更前は [0, 6, 8, 17]、変更後は [0, 6, 8, 12] です。変更量は -5 で、添字 2 を含み始める P[3] だけが食い違います。変更後の実際のタイルに当たる値は 6、2、4 で、全体の合計は 12 です。最後の保存値と一致します。

  2. 変更前の累積和は [0, 1, 8, 11, 17] です。古い差は 17 − 8 = 9、変更後の区間は 3 と 6 なので合計も 9 です。変更箇所は左端より前で、両端の保存値に同じ 3 が加わります。新しい表では 20 − 11 = 9 となり、不足分が相殺されます。

  3. 変更前の累積和は [0, 4, 12, 14, 19]、変更後は [0, 4, 12, 18, 23] です。[0, 2) は 4 と 8 で、古い差も新しい合計も 12 です。変更箇所は右端そのものなので含みません。[2, 4) の古い差は 19 − 12 = 7、新しい合計は 6 + 5 = 11 です。左端の要素が変更されたため、差は 4 増えます。

  4. 変更前は [0, 7]、変更後は [0, 1] です。[0, 1) の古い差は 7、新しい合計は 1 です。唯一の要素を含み、変更量 -6 が効きます。[1, 1) は要素がないので、古い差も新しい合計も 0 です。要素が1つでも累積和には先頭の 0 を含む2つの値があります。

  5. 変更量は 0 なので、変更前後とも [0, 5, 8, 16] です。[1, 3) は 3 と 8 を含み合計 11、表の差も 16 − 5 = 11 です。保存値に食い違いはありません。変更位置だけでなく、実際の変化量も判定に必要です。

要点

追跡のどこで迷ったか

保存値の範囲を誤る場合は、追跡表に「P[k] が含む最後の添字」と「変更箇所が含まれるか」を並べます。P[t] と P[t+1] の2行を比べれば、更新開始を1つ早めたのか遅めたのかが見えます。区間の判定だけが誤る場合は、l、r、t を別列に置き、l 以下 t かつ t が r 未満 を満たすか確認します。

個別指導で確かめる箇所は、変更前と変更後の各端点、古い差、新しい差、元配列を直接足した合計です。特に両端が古くても差が合う例と、片方だけが古く差がずれる例を見比べます。最後に実際に含まれる要素へ答えを戻すことで、保存表の計算だけでは見えない端点の誤読を見つけられます。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問