verify/verify-yosupo-ds/yosupo-static-sum.test.cpp

• View this file on GitHub
• Last update: 2025-03-17 21:57:32+08:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/sum.hpp

Code

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

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/sum.hpp"
#include <iostream>

int main(int argc, char const *argv[]) {
    int n, q, l, r;
    optimizeIO(), std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    Sum<long long> S(a);
    while (q--) {
        std::cin >> l >> r;
        std::cout << S.query(l, r - 1) << '\n';
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-static-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/sum.hpp"



#line 5 "src/alfred/data_structure/sum.hpp"

template <class T>
class Sum {
private:
    int n;
    std::vector<T> _pre, _suf;

public:
    Sum(void) : n(0) {}
    template <class InitT>
    Sum(std::vector<InitT> &init) { _init(init); }
    template <class InitT>
    inline void _init(std::vector<InitT> &init) {
        if (init.empty()) return;
        _pre.resize(n = init.size()), _suf.resize(n);
        _pre[0] = init[0], _suf[n - 1] = init[n - 1];
        for (int i = 1; i < n; i++) {
            _pre[i] = _pre[i - 1] + init[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            _suf[i] = _suf[i + 1] + init[i];
        }
    }
    inline T query(int l, int r) {
        if (l > r) return T();
        return l == 0 ? _pre[r] : _pre[r] - _pre[l - 1];
    }
    inline const T pre(int x) { return _pre[x]; }
    inline const T suf(int x) { return _suf[x]; }
};

template <class T>
class GridSum {
private:
    size_t n, m;
    std::vector<std::vector<T>> sum;

public:
    GridSum(void) : n(0), m(0) {}
    template <class InitT>
    GridSum(std::vector<std::vector<InitT>> &init) { _init(init); }
    template <class InitT>
    inline void _init(std::vector<std::vector<InitT>> &init) {
        if (init.empty()) return;
        n = init.size(), m = init[0].size();
        sum.assign(n, std::vector<T>(m)), sum[0][0] = init[0][0];
        for (size_t i = 1; i < n; i++) {
            sum[i][0] = sum[i - 1][0] + init[i][0];
        }
        for (size_t i = 1; i < m; i++) {
            sum[0][i] = sum[0][i - 1] + init[0][i];
        }
        for (size_t i = 1; i < n; i++) {
            for (size_t j = 1; j < m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + init[i][j];
            }
        }
    }
    inline T query(int x1, int y1, int x2, int y2) {
        T s1 = x1 == 0 ? 0 : sum[x1 - 1][y2];
        T s2 = y1 == 0 ? 0 : sum[x2][y1 - 1];
        T s3 = x1 == 0 || y1 == 0 ? 0 : sum[x1 - 1][y1 - 1];
        return sum[x2][y2] - s1 - s2 + s3;
    }
};


#line 6 "verify/verify-yosupo-ds/yosupo-static-sum.test.cpp"

int main(int argc, char const *argv[]) {
    int n, q, l, r;
    optimizeIO(), std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    Sum<long long> S(a);
    while (q--) {
        std::cin >> l >> r;
        std::cout << S.query(l, r - 1) << '\n';
    }

    return 0;
}

Back to top page