累積和

1357 ワード
cpp database algorithms テキストリンク
この記事では、累積総和について話しますが、最初に、私たちが配列を持っていて、私たちが合計を計算したいならば、コンピュータサイエンスの最も一般的な問題の1つについて話しましょう
この配列の特定の範囲の場合、入れ子になったループを考えます.
しかし,この解は(o(n)^ 2)より良い解を得ることができるか?
はい、累積加算を使用して行うことができます.を、それは正確には何ですか?
累積総和は、(o(1))の配列の特定の範囲の総和を得るために使用する技術です.
新しい配列を生成することによって、その配列の各要素は、その前に要素の総和を含んでいます
要素.

を、どのように我々はこのコードを書くことができますか?

ゼロベース
int range(int s,int e,vector<int>&v){
if(s==0)
    return v[e];
    return v[e]-v[s-1];
}
int main()
{

    vector<int>v={1,2,3,4,5,6};
    vector<int>s(v.size(),0);
    for(int i=0;i<v.size();i++){
        s[i]+=(i==0)?v[i]:v[i]+s[i-1];
    }
    cout<<range(2,4,s);
    return 0;
}
一基
int range(int s,int e,vector<int>&v){
    return v[e]-v[s-1];
}
int main()
{//one based
    vector<int>v={0,1,2,3,4,5,6};
    vector<int>s(v.size(),0);
    for(int i=1;i<v.size();i++){
        s[i]+=v[i]+s[i-1];
    }
    cout<<range(2,4,s);
    return 0;
}
TIL | SCSS @each
どのように、我々はGraphql、反応、ゴラン、Kory KratosとKubernetesを使っている学生プロジェクトプラットホームを構築しました、パート1