【C#】累積和を実装してみる - はなちるのマイノート

はじめに

今回は累積和を実装してみようという記事になります！

そもそも累積和をどこに使う必要があるのかというとこんな時です。

適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようになる手法

累積和を何も考えずに書けるようにする！ - Qiita

f:id:hanaaaaaachiru:20200331175248p:plain

軽く累積和の仕組みについて調べながら実際にC#で実装してみようと思います。

はじめに
累積和とは
実装してみる
小数版
使い方
さいごに

累積和とは

どのように前処理をして高速で区間内の総和を求めるかについて説明していきたいと思います。

まず前処理はn個の要素を持つ配列a[]に対して以下のような配列を作ることことを指します。

s[0] = 0
s[1] = a[0]
s[2] = a[0] + a[1]
・
・
s[n] = a[0] + a[1] + ... + a[n-1]

添字が結構ややこしいですが、そこは我慢するしかありません。

この下準備をしておくことで区間を以下のように計算することができます。

1以上3未満の区間の最大値
s[3] - s[1]    (= (a[0] + a[1] + a[2]) - (a[0]))

こうすることで前処理に計算量 $o(n)$ かかりますが、区間の最大値は計算量 $o(1)$ で取り出すことができます。

実装してみる

/// <summary>
/// 累積和
/// </summary>
public class CumulativeSum
{
    public long[] Array { get; }

    public CumulativeSum(IReadOnlyList<int> array) : this(array.Select(t => (long)t).ToArray()) { }

    public CumulativeSum(IReadOnlyList<long> array)
    {
        var length = array.Count;
        Array = new long[length + 1];

        for (int i = 0; i < length; i++)
        {
            Array[i + 1] = array[i] + Array[i];
        }
    }

    /// <summary>
    /// left以上right未満の総和
    /// </summary>
    /// <param name="left">以上</param>
    /// <param name="right">未満</param>
    public long GetSum(int left, int right)
    {
        if (left >= right) return 0;

        return Array[right] - Array[left];
    }
}

本当はジェネリックを使いたかったのですが、どんな制約をつけようとも+といった演算はできないんですね。

普通にできると思っていてビックリしてしまいました。

dynamicも検討しましたが処理速度が遅くなってしまうのは致命傷なので、結局long型に限定してしまいました。

小数版

ただlong型にしてしまったせいで少数の計算ができなくなってしまったので、小数版も書きました。

なんかうまく一緒にできる方法を見つけたら書き直したいと思います。

/// <summary>
/// 累積和
/// </summary>
public class CumulativeSum
{
    public double[] Array { get; }

    public CumulativeSum(IReadOnlyList<float> array) : this(array.Select(t => (double)t).ToArray()) { }

    public CumulativeSum(IReadOnlyList<double> array)
    {
        var length = array.Count;
        Array = new double[length + 1];

        for (int i = 0; i < length; i++)
        {
            Array[i + 1] = array[i] + Array[i];
        }
    }

    /// <summary>
    /// left以上right未満の総和
    /// </summary>
    /// <param name="left">以上</param>
    /// <param name="right">未満</param>
    public double GetSum(int left, int right)
    {
        if (left >= right) return 0;

        return Array[right] - Array[left];
    }
}

使い方

使い方はこんな感じ。

class Program
{
    static void Main(string[] args)
    {
        // 1 ~ 10を格納した配列
        var array = Enumerable.Range(1, 10).ToArray();
        var cSum = new CumulativeSum(array);

        // インデックスが5以上7未満の和を求める (6, 7)
        var sum = cSum.GetSum(5, 7);

        Console.WriteLine(sum);             // 13
    }
}