test/yosupo/static_range_sum.test.cpp

View this file on GitHub
Last update: 2021-02-13 18:30:55+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

src/CumulativeSum.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;
using lint = long long;

#include "../../src/CumulativeSum.hpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, Q;
    cin >> N >> Q;

    vector<lint> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    CuSum<lint> cuA(a);

    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << cuA.sum(l, r) << '\n';
    }

    return 0;
}

#line 1 "test/yosupo/static_range_sum.test.cpp"

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;
using lint = long long;

#line 2 "src/CumulativeSum.hpp"

#include <cassert>
#line 5 "src/CumulativeSum.hpp"

using namespace std;

template<class T>
class CuSum {
public:
    explicit CuSum(vector<T> const &vec) : cusum(vec.size() + 1) {
        for (int i = 0; i < (int)vec.size(); i++) cusum[i + 1] = cusum[i] + vec[i];
    }

    // partial sum of 0-indexed [0, k)
    [[nodiscard]] T sum(int k) {
        assert(0 <= k && k < cusum.size());
        return cusum[k];
    }
    // partial sum of 0-indexed [l, r)
    [[nodiscard]] T sum(int l, int r) {
        assert(l <= r);
        return sum(r) - sum(l);
    }

private:
    vector<T> cusum;
};

#line 12 "test/yosupo/static_range_sum.test.cpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, Q;
    cin >> N >> Q;

    vector<lint> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    CuSum<lint> cuA(a);

    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << cuA.sum(l, r) << '\n';
    }

    return 0;
}