移植演習：累積和をC++で

同じ入力にPythonとC++が同じ出力を返すことを確認します。移植はアルゴリズムを同時に変えず、差分を小さくします。

言語：C++ / 計算量：例の処理による

考え方

総和は long long にします。
s は n+1 個で0初期化。
Pythonと同じ半開区間 [l,r) の式を保ちます。

具体例

s[r]-s[l] の式は変わりません。入出力・型・ループ記法だけが変わります。

実装

#include <iostream>
#include <vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,q;cin>>n>>q;vector<long long>s(n+1);
    for(int i=0;i<n;i++){long long x;cin>>x;s[i+1]=s[i]+x;}
    while(q--){int l,r;cin>>l>>r;cout<<s[r]-s[l]<<"\n";}
}

注意する条件

高速入出力の設定後、CのstdioとC++のiostreamを混在させないのが無難です。endl は改行だけでなくフラッシュします。

確認問題

n個の配列の累積和に必要な要素数は？（n+1/n）

解答と理由

n+1

先頭0を置くので n+1 個です。

実装課題

講義のC++で区間和を実装。N Q、配列A、Q行のl r。0≤l≤r≤N。N,Q≤200000、|A_i|≤10^9。

入力:
3 2
2 5 1
0 2
1 3
出力:
7
6

参考実装

#include <iostream>
#include <vector>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<long long>s(n+1);for(int i=0;i<n;i++){long long x;cin>>x;s[i+1]=s[i]+x;}while(q--){int l,r;cin>>l>>r;cout<<s[r]-s[l]<<"\n";}}

読了の記録・下書き・メモへ