verify/Datastructure_static1dsum.test.cpp

View this file on GitHub
Last update: 2025-02-19 15:02:43+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include "../Utility/template.hpp"
#include "../Datastructure/static1dsum.hpp"



int main() {
    int n, q;
    cin >> n >> q;
    static1dsum<ll> sum1(n);


    rep(i, 0, n) {
        ll a;
        cin >> a;
        sum1.add(i, a);
    }

    sum1.build();

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << sum1.prod(l, r) << endl;
    }
    
}

#line 1 "verify/Datastructure_static1dsum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/static1dsum.hpp"
TT struct static1dsum {
    int n;
    vec<T> dat;
    bool built = false;

    static1dsum(int n = 0) : static1dsum(vec<T>(n, T())) {}

    static1dsum(vec<T> dat) : n(dat.size()), dat(dat) {}

    void add(int i, T x) {
        assert(built == false);
        dat[i] += x;
    }

    void build() {
        assert(built == false);
        rep(i, 0, n - 1) dat[i + 1] += dat[i];
        built = true;
    }

    T get(int p) const {
        assert(built);
        assert(0 <= p && p < n);
        T res = dat[p];
        if(p) res -= dat[p-1];
        return res;
    }

    T prod(int l, int r) const {
        assert(built);
        assert(0 <= l && r <= n);
        assert(l <= r);
        if(l == r) return 0;
        T res = dat[r - 1];
        if (l) res -= dat[l - 1];
        return res;
    }

    T all_prod() const {
        assert(built);
        return dat[n-1];
    }
};
/*
@brief 1次元累積和
@docs doc/static1dsum.md
*/
#line 4 "verify/Datastructure_static1dsum.test.cpp"



int main() {
    int n, q;
    cin >> n >> q;
    static1dsum<ll> sum1(n);


    rep(i, 0, n) {
        ll a;
        cin >> a;
        sum1.add(i, a);
    }

    sum1.build();

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << sum1.prod(l, r) << endl;
    }
    
}