JavaScriptで指定範囲内の区間和（Range Sum）を持つペアをカウントする方法

範囲和（Range Sum）とは？

範囲和 rangeSum(i, j) とは、配列のインデックス i から j（i ≤ j、両端を含む）までの要素の合計のことです。

問題の概要

整数の配列 arr を第1引数に、2つの数値 upper と lower を第2・第3引数として受け取るJavaScript関数を作成します。

この関数は、範囲 [lower, upper]（両端を含む）に収まる区間和の個数を返す必要があります。

入力例

const arr = [1, 4, 3];
const upper = 5;
const lower = 2;

出力例

この入力に対して、期待される出力は次のとおりです。

const output = 3;

すべての区間和を列挙して確認してみましょう。

• rangeSum(0, 0) = 1 … 範囲外
• rangeSum(0, 1) = 5 … 範囲内 ○
• rangeSum(0, 2) = 8 … 範囲外
• rangeSum(1, 1) = 4 … 範囲内 ○
• rangeSum(1, 2) = 7 … 範囲外
• rangeSum(2, 2) = 3 … 範囲内 ○

条件を満たすのは3つなので、答えは 3 になります。

解法のポイント：累積和と二分探索

すべての区間 (i, j) を素直に調べると O(n²) の計算量が必要になり、配列が長い場合には非効率です。そこで、次の2つのテクニックを組み合わせます。

1. 累積和の利用： 区間和 S(i, j) は「位置 j までの累積和 − 位置 i−1 までの累積和」と表せます。つまり本問題は、「ある累積和と別の累積和の差が [lower, upper] に入る組み合わせを数える」問題に言い換えられます。
2. 二分探索： それまでに現れた累積和を常にソート済みの状態で保持しておけば、条件を満たす要素の個数を二分探索で O(log n) で求められます。

コード例

const arr = [1, 4, 3];
const upper = 5;
const lower = 2;
const countRangeSum = (arr = [], lower, upper) => {
   const sums = [0];
   let res = 0;
   let last = 0;
   let firstge = value => {
      let l = 0, r = sums.length, m;
      do {
         m = Math.floor((r + l) / 2);
         sums[m] < value ? l = m : r = m;
      } while (r >= l + 2);
      while (r > 0 && sums[r - 1] >= value ) {
         r -= 1;
      }
      return r;
   };
   arr.forEach(num => {
      last += num;
      res += firstge(last - lower + 1) - firstge(last - upper);
      sums.splice(firstge(last), 0, last);
   });
   return res;
};
console.log(countRangeSum(arr, lower, upper));

実行結果

コンソールには次のように出力されます。

3

コードの解説

• sums：それまでに登場した累積和を昇順に保持する配列です。初期値を [0] にすることで、「配列の先頭から始まる区間」も正しく数えられるようになります。
• firstge(value)：二分探索により「value 以上の要素が最初に現れる位置」、すなわち「value 未満の要素の個数」を返すヘルパー関数です。
• last：現在の位置までの累積和を保持する変数です。
• res += firstge(last - lower + 1) - firstge(last - upper)：「last − 過去の累積和 ≥ lower」を満たす個数から「last − 過去の累積和 > upper」を満たす個数を差し引くことで、lower ≤ 区間和 ≤ upper を満たす組み合わせだけを数えています。
• sums.splice(firstge(last), 0, last)：現在の累積和を適切な位置に挿入し、sums を常にソート済みの状態に保ちます。

計算量の目安

二分探索そのものは O(log n) ですが、splice による挿入は最大 O(n) のコストがかかるため、この実装全体の計算量は O(n²) になります。より大きな配列を扱いたい場合は、マージソートの併合処理の中で条件を満たすペアを数える手法（計算量 O(n log n)）を採用すると効果的です。