누적합

🔎 전체코드

#include <bits/stdc++.h>

using namespace std;

void print(vector<int> const &a) {
    for (auto i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << "\\n";
}

// 누적합
vector<int> make_psum(vector<int> &a) {
    vector<int> psum;
    psum.push_back(0);

    for (auto i = 0; i < a.size(); i++) {
        psum.push_back(psum[i] + a[i]);
    }

    return psum;
}

// 구간합
int section_sum(vector<int> &psum, int from, int to) {
    return psum[to] - psum[from - 1];
}

void print_section_sum(vector<int> &psum, int from, int to) {
    cout << "from: " << from << " , to: " << to << ", result: " << section_sum(psum, from, to) << "\\n";
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};

    vector<int> psum = make_psum(a);
    print(psum);
    print_section_sum(psum, 1, 4);

    return 0;
}

🔎 누적합

// 누적합
vector<int> make_psum(vector<int> &a) {
    vector<int> psum;
    psum.push_back(0);

    for (auto i = 0; i < a.size(); i++) {
        psum.push_back(psum[i] + a[i]);
    }

    return psum;
}

• 누적합 배열의 0번째 원소는 0으로 둔다

🔎 구간합

// 구간합
int section_sum(vector<int> &psum, int from, int to) {
    return psum[to] - psum[from - 1];
}

• 원소들의 구간합을 구할 때 편의상 0이 아닌 1부터 센다.