Test/yosupo-Static-Range-Sum.test.cpp

View this file on GitHub
Last update: 2023-01-27 17:37:24+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

CumulativeSum (Data_structure/CumulativeSum.hpp)

Code

#include <bits/stdc++.h>
using namespace std;

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

#include "../Data_structure/CumulativeSum.hpp"

int main() {

    int N, Q; cin >> N >> Q;
    vector<long long> A(N);
    for (auto &a : A) cin >> a;

    CumulativeSum<long long> cum(A);

    while (Q--) {
        int l, r; cin >> l >> r;
        cout << cum.sum(l, r) << endl;
    }

}

#line 1 "Test/yosupo-Static-Range-Sum.test.cpp"
#include <bits/stdc++.h>
using namespace std;

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

#line 1 "Data_structure/CumulativeSum.hpp"
template<class T> struct CumulativeSum {
    int n;
    vector<T> data; 
    bool builded = false;
    CumulativeSum(int n) : n(n), data(n + 1) {}
    CumulativeSum(const vector<T> &v) : n(v.size()), data(n + 1) {
        for (int i = 0; i < n; i++) {
            data[i + 1] = v[i];
        }
    }

    void build() {
        for (int i = 0; i < n; i++) {
            data[i + 1] += data[i];
        }
        builded = true;
    }

    T sum(int r) {
        if (!builded) build();
        assert(0 <= r && r <= n);
        return data[r];
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) - sum(l);
    }

};
#line 7 "Test/yosupo-Static-Range-Sum.test.cpp"

int main() {

    int N, Q; cin >> N >> Q;
    vector<long long> A(N);
    for (auto &a : A) cin >> a;

    CumulativeSum<long long> cum(A);

    while (Q--) {
        int l, r; cin >> l >> r;
        cout << cum.sum(l, r) << endl;
    }

}