「 \(S_i = a_1\) から \(a_n\) までの合計」とおきます。( \(S_0 = 0\) とします )

このとき、\(a_l+a_{l+1} + ... + a_{r-1}\) は \(S_r - S_l\) で計算することができます。

これによって、宿場町間の距離を \(2\) つの値の差として計算することができ、結果として \(O(1)\) 時間で計算できるようになります。

この手法は 累積和 と呼ばれる手法です。