【C++】arr[i] = i×(-1)^i となる配列で、インデックスLからRまでの要素の総和を求める方法

問題概要

この問題では、2つの整数 L と R が与えられます。また、arr[i] = i × (-1)ⁱ として定義される配列 arr[] を考えます。求めたいのは、この配列におけるインデックス L から R までの要素の総和です。

arr[i] は、インデックスが偶数のとき正の値、奇数のとき負の値になります。そのため、範囲 [L, R] 内の要素に対して「偶数インデックスは加算、奇数インデックスは減算」という処理を行った結果が答えとなります。

問題を理解するための具体例

入力:

L = 2 , R = 6

出力:

4

説明:

arr[] = {-1, 2, -3, 4, -5, 6}
Sum = 2 + (-3) + 4 + (-5) + 6 = 4

解法1：素朴なアプローチ（ループで計算）

最もシンプルな解決策は、L から R までループを回し、偶数インデックスの要素をすべて加算し、奇数インデックスの要素をすべて減算していく方法です。最後に合計値を返します。

実装例

#include <iostream>
#include <math.h>
using namespace std;

int CalcArrSumLtoR(int L, int R) {
    int sum = 0;
    for (int i = L; i <= R; i++){
        sum += (i * pow((-1), i));
    }
    return sum;
}

int main() {
    int L = 3, R = 15;
    cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "<<CalcArrSumLtoR(L, R);
    return 0;
}

出力

Sum of elements of array from index 3 to 15 is -9

このアプローチは直感的で分かりやすいですが、範囲内の全要素を順番に走査する必要があるため、時間計算量は O(n) となり、必ずしも効率的とはいえません。

解法2：数式を活用した効率的なアプローチ

より効率的な解決策は、奇数および偶数の和に関する数学的公式を利用することです。

• 最初の n 個の奇数の和 = n × n
• 最初の n 個の偶数の和 = n × (n + 1)

これらの公式を用いると、最終的な合計は次のように計算できます。

sum =（最初のR個の偶数の和 − 最初の(L-1)個の偶数の和）−（最初のR個の奇数の和 − 最初の(L-1)個の奇数の和）

ここで重要なのは、n までの間には偶数と奇数がそれぞれ約 n/2 個ずつ存在するという点です。つまり、R 以下には R/2 個の偶数があるため、R/2 や L/2 の値を使って各区間の和を求めます。この方法なら、配列を走査せずに定数時間 O(1) で答えを得られます。

実装例

#include <iostream>
using namespace std;

long int findSum(int n, bool isEven) {
    long int total = 0;
    if(isEven == true){
        total = (n) / 2;
        return (total * (total+1));
    }
    else {
        total = (n + 1) / 2;
        return total * total;
    }
}

int CalcArrSumLtoR(int L, int R) {
    return (findSum(R, true) - findSum(L - 1, true)) - (findSum(R, false) - findSum(L - 1, false));
}

int main() {
    int L = 3, R = 15;
    cout<<"Sum of elements of array from index "<<L<<" to "<<R<<" is "<<CalcArrSumLtoR(L, R);
    return 0;
}

出力

Sum of elements of array from index 3 to 15 is -9

まとめ

本記事では、arr[i] = i × (-1)ⁱ で定義される配列の区間 [L, R] の総和を求める問題について、O(n) のループによる素朴な解法と、奇数・偶数の和の公式を活用した O(1) の効率的な解法の2つを紹介しました。数学的な性質を利用して計算量を大幅に削減できるのは、アルゴリズム設計の好例といえるでしょう。