区間の和を求めるアルゴリズム(区間の更新なし)

2020年3月20日その他区間和, 区間, 累積和, 配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 [L, R) の和を求めるアルゴリズムについてです。

区間の和は 11+1+8=20

アルゴリズム

単純なアルゴリズム(前処理なし):

  1. \(a_L + a_{L+1} + \cdots + a_{R-1}\) を計算する

効率的なアルゴリズム(前処理あり):

  • 前処理
    1. \(S_{i+1} = a_0 + a_1 + a_2+ \cdots + a_i \) となる、累積和 \(\{S_0, S_1, S_2, \cdots, S_N\}\) を求めておく
  • クエリ(\(a_L + a_{L+1} + a_{L+2} + \cdots + a_{R-1}\) を求める)
    1. \( S_{R} – S_{L} \) を計算する

※ 前処理では \(S_{i+1} = S_i + a_i\) などとすると高速に計算ができます。
※ クエリでは \( S_{R} – S_{L} = a_L + a_{L+1} + \cdots + a_{R-1}\) となることを利用しています。

計算量

  • 単純なアルゴリズム
    • 前処理:なし
    • クエリ:\(O(N)\)
  • 効率的なアルゴリズム(前処理あり)
    • 前処理:\(O(N)\)
    • クエリ:\(O(1)\)

単純なアルゴリズムでは、区間に比例した回数足し算をしなければなりませんが、累積和を利用すると 1 回の引き算で計算ができます。

C++ での実装例(効率的なアルゴリズム)

累積和の気持ち

累積和とは

累積和は、「始めから i 番目までの和を前処理で計算したもの」です。つまり、「区間 [0, i) の和を全ての i について計算したもの」とも言えます。

元の数列と累積和の関係

この累積和は、先程述べた通り、

  • 1つあたり \(O(1)\)、全体で \(O(N)\) で高速に計算できる
  • 累積和を利用して、任意の区間和が \(O(1)\) で求めることができる

という利点があります。

累積和は高速に計算できる

i 番目までの累積和が分かっていれば、i+1 番目の累積和というのは簡単に求めることができます。

区間 [0, 4) の累積和を \(S_4\) などと表すようにしましょう。すると上の図のように、

\begin{align}
S_5 &= (5+11+1+8) + 7 \\
&= S_4 + a_4
\end{align}

となって、\(S_5\) は \(S_4\) を用いることで \(O(1)\) で計算することができます。

つまり、全体としては以下のような順番で計算すれば \(O(N)\) になります。

  • \(S_0 = 0\)
  • \(S_1 = S_0 + a_0\)
  • \(S_2 = S_1 + a_1\)
  • \(S_3 = S_2 + a_2\)
  • \(S_{i+1} = S_i + a_i\)
  • \(S_{N} = S_{N-1} + a_{N-1}\)

プログラムで書けば以下のようにすれば良いです。

累積和を用いると区間和が簡単に求まる

結論から言うと、区間 [L, R) の和は、累積和を用いると以下のように計算ができます。

  • 区間 [L, R) の和 = \(S_R – S_L\)

数式を追って確かめてみましょう。まず、累積和は

  • \(S_L\) = 区間 [0, L) の和 = \(a_0 + a_{1} + a_{2} + \cdots + a_{L-1}\)
  • \(S_R\) = 区間 [0, R) の和 = \(a_0 + a_{1} + a_{2} + \cdots + a_{L-1} + a_{L}+ \cdots + a_{R-1}\)

となるので、

  • \(S_R – S_L\) = \(a_L + a_{L+1} + a_{L+2} + \cdots + a_{R-1}\) = 区間 [L, R) の和

となり確かめられました。

コードでは以下のようになります。

具体例

実際に区間 [1, 4) の区間和を累積和で求めてみましょう。

前処理して累積和を求めると、\(S_R\) は以下のようになります。

\(S_R\) の様子

\(S_L\) は以下のようになります。

\(S_L\) の様子

2つの差を考えると、ちょうど以下の部分になり、求めたいものが計算できます。

参考

二次元の区間和の場合

二次元の区間和を求める場合でも、同様に累積和を用いることで高速にクエリが処理できます。

区間の更新がある場合

数列を途中で変更するなどの「更新」があった場合は、累積和を計算し直す必要があるので逆に非効率になります。

そのような場合は、セグメント木BIT などのデータ構造を用いると、

  • 更新:\(O(\log N)\)
  • クエリ:\(O(\log N)\)

で処理ができます。

練習問題