test/library-checker/static_range_sum.test.cpp

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

Depends on

• 累積和 (datastructure/cumulative_sum.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>

#include "datastructure/cumulative_sum.hpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    cumulative_sum cs(a);
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << cs.sum(l, r) << '\n';
    }
}

#line 1 "test/library-checker/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>

#line 3 "datastructure/cumulative_sum.hpp"
template <typename T>
struct cumulative_sum {
    int n;
    std::vector<T> cumsum;
    cumulative_sum() {
    }
    cumulative_sum(std::vector<T>& d) : n(d.size()), cumsum(n + 1) {
        for (int i = 0; i < n; i++) {
            cumsum[i + 1] = cumsum[i] + d[i];
        }
    }
    T sum(int l, int r) {
        // 0-indexed
        // [l, r)
        assert(0 <= l);
        assert(l <= r);
        assert(r <= n);
        return cumsum[r] - cumsum[l];
    }
};
#line 5 "test/library-checker/static_range_sum.test.cpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    cumulative_sum cs(a);
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << cs.sum(l, r) << '\n';
    }
}

Back to top page