累積和 (lib/algorithm/prefix_sum.hpp)

• View this file on GitHub
• Last update: 2026-03-15 19:52:24+09:00
• Include: #include "lib/algorithm/prefix_sum.hpp"

Verified with

• test/aoj/challenge/0009.test.cpp
• test/aoj/joi/prefix_sum.test.cpp
• test/yosupo/data_structure/static_range_sum.test.cpp

Code

#pragma once
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>

/// @brief 累積和
template <class T = std::int64_t>
struct prefix_sum {
    prefix_sum() = default;
    prefix_sum(int _n) : n(_n), data(_n + 1) {}
    template <class U>
    prefix_sum(const std::vector<U> &v) : n(v.size()), data(v.size() + 1) {
        std::inclusive_scan(v.rbegin(), v.rend(), data.rbegin() + 1);
    }

    void build() {
        for (int i = n - 1; i >= 0; --i) data[i] += data[i + 1];
    }

    T get(int k) const {
        assert(0 <= k && k < n);
        return data[k] - data[k + 1];
    }

    void set(int k, int x) { data[k] = x; }
    void add(int k, int x) { data[k] += x; }

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

    int lower_bound(T x) const { return lower_bound(0, x); }
    int lower_bound(int l, T x) const {
        assert(0 <= l && l <= n);
        int left = l, right = n + 1;
        while (right - left > 1) {
            int mid = std::midpoint(left, right);
            (data[l] - data[mid] >= x ? right : left) = mid;
        }
        return right;
    }

    int upper_bound(T x) const { return upper_bound(0, x); }
    int upper_bound(int l, T x) const {
        assert(0 <= l && l <= n);
        int left = l, right = n + 1;
        while (right - left > 1) {
            int mid = std::midpoint(left, right);
            (data[l] - data[mid] > x ? right : left) = mid;
        }
        return right;
    }

  private:
    int n;
    std::vector<T> data;
};

#line 2 "lib/algorithm/prefix_sum.hpp"
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>

/// @brief 累積和
template <class T = std::int64_t>
struct prefix_sum {
    prefix_sum() = default;
    prefix_sum(int _n) : n(_n), data(_n + 1) {}
    template <class U>
    prefix_sum(const std::vector<U> &v) : n(v.size()), data(v.size() + 1) {
        std::inclusive_scan(v.rbegin(), v.rend(), data.rbegin() + 1);
    }

    void build() {
        for (int i = n - 1; i >= 0; --i) data[i] += data[i + 1];
    }

    T get(int k) const {
        assert(0 <= k && k < n);
        return data[k] - data[k + 1];
    }

    void set(int k, int x) { data[k] = x; }
    void add(int k, int x) { data[k] += x; }

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

    int lower_bound(T x) const { return lower_bound(0, x); }
    int lower_bound(int l, T x) const {
        assert(0 <= l && l <= n);
        int left = l, right = n + 1;
        while (right - left > 1) {
            int mid = std::midpoint(left, right);
            (data[l] - data[mid] >= x ? right : left) = mid;
        }
        return right;
    }

    int upper_bound(T x) const { return upper_bound(0, x); }
    int upper_bound(int l, T x) const {
        assert(0 <= l && l <= n);
        int left = l, right = n + 1;
        while (right - left > 1) {
            int mid = std::midpoint(left, right);
            (data[l] - data[mid] > x ? right : left) = mid;
        }
        return right;
    }

  private:
    int n;
    std::vector<T> data;
};

Back to top page