test/yosupo/static-range-sum.test.cpp

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

#include "../../Data-Structure/Range-Accumulate/cumulative-sum.hpp"
#include "../../Data-Structure/Range-Accumulate/foldLR.hpp"
#include "../../Data-Structure/Range-Accumulate/FenwicTree.hpp"

#include "../../Util/IO/println.hpp"
#include "../../Util/IO/read.hpp"
#include "../../Util/int-alias.hpp"
#include "../../Util/all-macro.hpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int N, Q;
    std::cin >> N >> Q;

    auto a = read<int>(N);

    CumulativeSum<i64> cum(a);

    FoldLR<i64> fold(all(a), 0, [](i64 x1, i64 x2) { return x1 + x2; });

    FenwicTree<i64> ft(N);
    for (int i = 0; i < N; ++i) {
        ft.add(i, a[i]);
        assert(ft.at(i) == a[i]);
    }

    while (Q--) {
        int l, r;
        std::cin >> l >> r;

        const auto ans1 = cum.sum(l, r);
        const auto ans2 = fold.foldL(r) - fold.foldL(l);
        const auto ans3 = fold.foldR(l) - fold.foldR(r);
        const auto ans4 = ft.sum(l, r);

        assert(ans2 == ans1);
        assert(ans3 == ans1);
        assert(ans4 == ans1);

        println(ans1);
    }

    return 0;
}

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

#line 5 "Data-Structure/Range-Accumulate/cumulative-sum.hpp"

/**
 * @brief CumulativeSum (累積和)
 */
template <class T>
struct CumulativeSum {
    std::valarray<T> data;

    CumulativeSum() = default;

    template <class Container>
    explicit CumulativeSum(const Container& container)
        : CumulativeSum(container.cbegin(), container.cend()) {}

    template <class InputItr>
    CumulativeSum(InputItr begin, InputItr end)
        : data(std::distance(begin, end) + 1) {
        size_t i;
        InputItr itr;
        for (i = 0, itr = begin; itr != end; ++i, ++itr) {
            data[i + 1] = data[i] + *itr;
        }
    }

    //! [0, r)
    const T prefixSum(size_t r) const { return data[r]; }

    //! [l, r)
    const T sum(size_t l, size_t r) const { return prefixSum(r) - prefixSum(l); }
};
#line 3 "Data-Structure/Range-Accumulate/foldLR.hpp"

/**
 * @brief FoldLR
 */
template <class T>
class FoldLR {
    std::vector<T> m_foldL, m_foldR;
    T m_e;

public:
    FoldLR() = default;

    template <class BidirectionalItr, class Op>
    FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, Op op)
        : FoldLR(begin, end, e, op, op) {}

    /**
     * foldLeftOp: (T, Elem) -> T
     * foldRightOp: (Elem, T) -> T
     */
    template <class BidirectionalItr, class FoldLeftOp, class FoldRightOp>
    FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, FoldLeftOp foldLeftOp, FoldRightOp foldRightOp)
        : m_foldL(std::distance(begin, end) + 1, e)
        , m_foldR(std::distance(begin, end) + 1, e)
        , m_e(e) {
        size_t i;
        BidirectionalItr itr;
        for (i = 0, itr = begin; itr != end; ++i, ++itr) {
            m_foldL[i + 1] = foldLeftOp(m_foldL[i], *itr);
        }
        for (i = m_foldR.size() - 1, itr = std::prev(end); i > 0; --i, --itr) {
            m_foldR[i - 1] = foldRightOp(*itr, m_foldR[i]);
        }
    }

    /**
     * [0, r)
     * ((((e op a[0]) op a[1]) op a[2]) ... op a[r - 1])
     * foldL(0) returns e();
     */
    const T foldL(size_t r) const { return m_foldL[r]; }

    /**
     * [l, N)
     * (a[l] op ... (a[N - 3] op (a[N - 2] op (a[N - 1] op e))))
     * foldR(N) returns e();
     */
    const T foldR(size_t l) const { return m_foldR[l]; }

    const T e() const { return m_e; }
};
#line 4 "Data-Structure/Range-Accumulate/FenwicTree.hpp"

/**
 * @brief Fenwic-Tree (Binary-Indexed-Tree)
 */
template <class T>
class FenwicTree {
    size_t m_size;
    std::vector<T> dat;

public:
    FenwicTree() = default;

    explicit FenwicTree(size_t n)
        : m_size(n)
        , dat(n + 1) {}

    //! i: [0, n)
    void add(size_t i, const T& value) {
        assert(i < m_size);
        ++i;
        while (i <= m_size) dat[i] += value, i += i & -i;
    }

    //! [0, r)
    const T prefixSum(size_t r) const {
        T acc = 0;
        while (r > 0) acc += dat[r], r -= r & -r;
        return acc;
    }

    //! [l, r)
    const T sum(size_t l, size_t r) const { return prefixSum(r) - prefixSum(l); }

    //! i: [0, n)
    const T at(size_t i) const { return prefixSum(i + 1) - prefixSum(i); }

    //! return `i` s.t. prefixSum(i) >= value
    size_t lowerBound(T value) const {
        if (value <= 0) return 0;
        static const auto B = floorPow2(m_size);
        size_t i = 0;
        for (size_t k = B; k > 0; k >>= 1) {
            if (i + k <= m_size && dat[i + k] < value) {
                value -= dat[i + k];
                i += k;
            }
        }
        return i + 1;
    }

private:
    static inline constexpr size_t floorPow2(size_t x) noexcept {
        size_t ret = 1;
        while (ret <= x) ret <<= 1;
        return ret >> 1;
    }
};
#line 7 "test/yosupo/static-range-sum.test.cpp"

#line 4 "Util/IO/println.hpp"

/**
 * @brief println() (可変個の値を空白区切りで出力して改行する)
 */
inline void println() {
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void println(Head&& head, Tail&&... tail) {
    std::cout << head << &" "[!sizeof...(tail)];
    println(std::forward<Tail>(tail)...);
}
#line 4 "Util/IO/read.hpp"

/**
 * @brief read() (n個入力してContainerに格納して返す)
 */
template <class T = int, template <class, class...> class Container = std::vector>
Container<T> read(size_t n) {
    Container<T> ret(n);
    for (auto& e : ret) std::cin >> e;
    return ret;
}
#line 3 "Util/int-alias.hpp"

/**
 * @brief int-alias (整数型のエイリアス)
 */
using i64 = int64_t;
using u64 = uint64_t;
#line 2 "Util/all-macro.hpp"

/**
 * @brief all()マクロ
 */
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
#line 12 "test/yosupo/static-range-sum.test.cpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int N, Q;
    std::cin >> N >> Q;

    auto a = read<int>(N);

    CumulativeSum<i64> cum(a);

    FoldLR<i64> fold(all(a), 0, [](i64 x1, i64 x2) { return x1 + x2; });

    FenwicTree<i64> ft(N);
    for (int i = 0; i < N; ++i) {
        ft.add(i, a[i]);
        assert(ft.at(i) == a[i]);
    }

    while (Q--) {
        int l, r;
        std::cin >> l >> r;

        const auto ans1 = cum.sum(l, r);
        const auto ans2 = fold.foldL(r) - fold.foldL(l);
        const auto ans3 = fold.foldR(l) - fold.foldR(r);
        const auto ans4 = ft.sum(l, r);

        assert(ans2 == ans1);
        assert(ans3 == ans1);
        assert(ans4 == ans1);

        println(ans1);
    }

    return 0;
}