メインコンテンツへスキップ
見出し画像

累積和で区間の合計を求める

    解き方

    累積和は、配列の先頭から各位置までの合計を別の配列に保持する方法です。同じ配列について、さまざまな区間の合計を繰り返し求めるときに使えます。ここでは要素番号を1から数え、補助配列Sの0番目を0と定めます。


    手順を追う例

    A=[3, 1, 4, 2]に対し、S[0]=0、S[i]=S[i−1]+A[i] とすると、Sは[0, 3, 4, 8, 10]です。l番目からr番目までの合計はS[r]−S[l−1]で求めます。rまでの合計から、区間の手前までの合計を引きます。


    確認問題【オリジナル】

    A=[2, 5, 1, 6, 3]のとき、2番目から4番目までの合計を累積和で求めてください。S[4]−S[2]ではなぜ正しくありませんか。


    答えと解説

    Sは[0, 2, 7, 8, 14, 17]です。答えはS[4]−S[1]=14−2=12。S[4]−S[2]では2番目の5まで引いてしまい、3番目と4番目の合計7になります。累積和を作る処理は要素数nに比例し、作成後の各区間の合計は配列の2か所を読むだけで計算できます。

    IPA 科目Bサンプル問題(出題形式の参考)

    科目Bの目次

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ