library/datastructure/CumulativeSum.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/datastructure/CumulativeSum.hpp"

Depends on

• build/pch/stdc++.hpp

Verified with

• test/library-checker/DataStructure/RectangleSum_2.test.cpp
• test/library-checker/DataStructure/StaticRangeSum.test.cpp

Code

template <typename T> struct CumulativeSum {
    using U = std::conditional_t<std::is_same_v<T, int>, long long, T>;
    std::vector<U> A;
    CumulativeSum() : A(1, 0) {}
    CumulativeSum(const std::vector<T> &v) : A(v.size() + 1, 0) {
        for (int i = 0; i < v.size(); i++)
            A[i + 1] = A[i] + v[i];
    }
    void add(const T &a) { A.push_back(A.back() + a); }
    U sum(int l, int r) {
        assert(0 <= l and l <= r and r < A.size());
        return A[r] - A[l];
    }
    U sum() { return A.back(); }
};

#line 1 "library/datastructure/CumulativeSum.hpp"
template <typename T> struct CumulativeSum {
    using U = std::conditional_t<std::is_same_v<T, int>, long long, T>;
    std::vector<U> A;
    CumulativeSum() : A(1, 0) {}
    CumulativeSum(const std::vector<T> &v) : A(v.size() + 1, 0) {
        for (int i = 0; i < v.size(); i++)
            A[i + 1] = A[i] + v[i];
    }
    void add(const T &a) { A.push_back(A.back() + a); }
    U sum(int l, int r) {
        assert(0 <= l and l <= r and r < A.size());
        return A[r] - A[l];
    }
    U sum() { return A.back(); }
};

Back to top page