【小ネタ】高校数学で習うシグマ計算のスニペット

単純なシグマ計算

C++

#include <iostream>

long long sigma_loop(int n) {
    long long sum = 0;
    // 1からnまで順番に足し合わせる
    for (int i = 1; i <= n; ++i) {
        sum += i; // 任意の式（例: i * i など）に変更可能
    }
    return sum;
}

C#

public long SigmaLoop(int n) {
    long sum = 0;
    // 1からnまで順番に足し合わせる
    for (int i = 1; i <= n; ++i) {
        sum += i; // 任意の式に変更可能
    }
    return sum;
}

単純な一次関数だけでなく、条件分岐を含めたり、複雑な関数 $f(i)$ のシグマを計算したりする際にいじりやすい

このアルゴリズム自体はブルートフォースの脳筋計算なので、何の工夫もなしには実用性には欠ける
計算量: O(n)

数学公式による計算（高速化）:等差数列の和の公式

速い　

計算量: O(1)（$n$ がどんなに大きくても一瞬で計算完了）
型の許容数値をオーバーフローする可能性があるので、必要なら long longなどのデカい型を使う
C++

long long sigma_formula(long long n) {
    // オーバーフローを防ぐため、計算順序や型キャストに注意
    // 偶数のほうを先に2で割ることで安全性を高める書き方もあります
    return n * (n + 1) / 2;
}

C#

public long SigmaFormula(long n) {
    // C#のlongは64ビット整数なので、nが非常に大きくても計算可能
    return n * (n + 1) / 2;
}

累積和（配列の区間シグマ）「配列の L 番目から R番目までの和」を何度も繰り返し求める

計算量: 前処理に O(n)、毎回のシグマ取得は O(1)

C++

#include <vector>

class PrefixSum {
private:
    std::vector<long long> s;
public:
    // 前処理: O(n)
    PrefixSum(const std::vector<int>& arr) {
        int n = arr.size();
        s.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + arr[i]; // 先頭からの合計を蓄積
        }
    }

    // クエリ: LからRまでのシグマ (0-indexed, Rを含む) O(1)
    long long get_sigma(int L, int R) {
        return s[R + 1] - s[L];
    }
};

C#

public class PrefixSum {
    private long[] s;

    // 前処理: O(n)
    public PrefixSum(int[] arr) {
        int n = arr.Length;
        s = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + arr[i]; // 先頭からの合計を蓄積
        }
    }

    // クエリ: LからRまでのシグマ (0-indexed, Rを含む) O(1)
    public long GetSigma(int L, int R) {
        return s[R + 1] - s[L];
    }
}

std::accumlate/LINQを使用したモダンスタイルの実装

O(n)だが、バグりにくい上読みやすい

 #include <numeric>
#include <vector>

long long sigma_stl(const std::vector<int>& arr) {
    // arrの先頭から末尾まで、初期値0(long long型)に足し合わせる
    return std::accumulate(arr.begin(), arr.end(), 0LL);
}

using System.Linq;

// パターンA: 配列の中身のシグマ
public long SigmaLinqArray(int[] arr) {
    // .Sum() を呼び出すだけ (結果がintの最大値を超える場合はキャストが必要)
    return arr.Select(x => (long)x).Sum();
}

// パターンB: 1からnまでのシグマ
public long SigmaLinqRange(int n) {
    // 1からn個の整数を生成し、合計する
    return Enumerable.Range(1, n).Select(x => (long)x).Sum();
}