test/data_structure/static_range_sum.0.test.cpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

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

#include "disjoint_sparse_table.hpp"
#include "monoid.hpp"
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> V(n);
    for (int i = 0; i < n; ++i) std::cin >> V[i];
    DisjointSparseTable dst(V, Monoid(std::plus<long long>(), 0LL));
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << dst.query(l, r) << '\n';
    }
    return 0;
}

#line 1 "test/data_structure/static_range_sum.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#line 2 "disjoint_sparse_table.hpp"

#line 2 "monoid.hpp"

#include <type_traits>

template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class Monoid {
public:
    Op F;
    Tp Id;

    explicit Monoid(Op F, const Tp &Id = {}) : F(F), Id(Id) {}

    const Tp &id() const { return Id; }
    Tp operator()(const Tp &L, const Tp &R) const { return F(L, R); }
};
#line 4 "disjoint_sparse_table.hpp"
#include <algorithm>
#include <cassert>
#include <vector>

template<typename Tp, typename Op> class DisjointSparseTable {
public:
    int S;
    const Monoid<Tp, Op> M;
    std::vector<Tp> T;

    DisjointSparseTable(const std::vector<Tp> &V, const Monoid<Tp, Op> &M) : M(M) {
        const int N = V.size();
        int LogN    = 0;
        while ((1 << LogN) < N) ++LogN;
        S = (1 << LogN);
        T.resize(std::max(LogN, 1) * S);
        for (int i = 0; i < N; ++i) T[i] = V[i];
        for (int i = N; i < S; ++i) T[i] = this->M.id();
        for (int i = 2; i <= LogN; ++i) {
            auto C = T.begin() + (i - 1) * S;
            for (int j = 0; j < S; j += (1 << i)) {
                const int mid = j + (1 << (i - 1));
                C[mid - 1]    = T[mid - 1];
                for (int k = mid - 2; k >= j; --k) C[k] = M(T[k], C[k + 1]);
                C[mid] = T[mid];
                for (int k = mid + 1; k < j + (1 << i); ++k) C[k] = M(C[k - 1], T[k]);
            }
        }
    }

    // returns M(V[L],...,V[R-1])
    Tp query(int L, int R) const {
        assert(L <= R);
        if (L == R) return M.id();
        if (R - L == 1) return T[L];
        const int lv = 31 - __builtin_clz(L ^ (R - 1));
        return M(T[lv * S + L], T[lv * S + (R - 1)]);
    }
};
#line 5 "test/data_structure/static_range_sum.0.test.cpp"
#include <functional>
#include <iostream>
#line 8 "test/data_structure/static_range_sum.0.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> V(n);
    for (int i = 0; i < n; ++i) std::cin >> V[i];
    DisjointSparseTable dst(V, Monoid(std::plus<long long>(), 0LL));
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << dst.query(l, r) << '\n';
    }
    return 0;
}