verify/lc_data_structure/lc_static_range_sum.test.cpp

• View this file on GitHub
• Last update: 2023-03-17 17:11:39+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• 累積和 (data_structure/cumulative_sum.hpp)

Code

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

#include <bits/stdc++.h>

#include "data_structure/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];
    CumulativeSum<long long> rui(A);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << rui.sum(l, r) << '\n';
    }
    return 0;
}

#line 1 "verify/lc_data_structure/lc_static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include <bits/stdc++.h>

#line 2 "data_structure/cumulative_sum.hpp"

template <class T> struct CumulativeSum {
    int n;
    std::vector<T> seg;

    CumulativeSum() = default;

    CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}

    CumulativeSum(std::vector<T> &a) {
        n = (int)a.size();
        seg.assign(n + 1, T(0));
        for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
    }

    // [l, r)
    T sum(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return seg[r] - seg[l];
    }

    // A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
    void imos(int l, int r, T x = T(1)) {
        assert(0 <= l and l <= r and r <= n);
        seg[l] += x;
        seg[r] -= x;
    }

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

    // return A[p]
    T get(int p) const {
        assert(0 <= p and p < n);
        return seg[p];
    }

    // output
    friend std::ostream &operator<<(std::ostream &os, const CumulativeSum &A) {
        os << "n = " << A.n << "\n";
        for (int i = 0; i <= A.n; i++) os << A.seg[i] << " \n"[i == A.n];
        return os;
    }
};
#line 6 "verify/lc_data_structure/lc_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];
    CumulativeSum<long long> rui(A);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << rui.sum(l, r) << '\n';
    }
    return 0;
}

Back to top page