累積和
(datastructure/cumulative_sum.hpp)

• View this file on GitHub
• Last update: 2024-05-30 15:02:19+09:00
• Include: #include "datastructure/cumulative_sum.hpp"

概要

• 累積和を前計算することで区間和を高速に計算する。

使い方

• cumulative_sum(d): 数列 $\mathrm d$ で初期化する。
• sum(l, r): $\mathrm d_l + \mathrm d_{l+1} + \cdots +\mathrm d_{r-1}$ を求める。

計算量

• cumulative_sum(d): $\mathcal O(N)$
• sum(l, r): $\mathcal O(1)$

Verified with

• test/library-checker/static_range_sum.test.cpp

Code

#pragma once
#include <vector>
template <typename T>
struct cumulative_sum {
    int n;
    std::vector<T> cumsum;
    cumulative_sum() {
    }
    cumulative_sum(std::vector<T>& d) : n(d.size()), cumsum(n + 1) {
        for (int i = 0; i < n; i++) {
            cumsum[i + 1] = cumsum[i] + d[i];
        }
    }
    T sum(int l, int r) {
        // 0-indexed
        // [l, r)
        assert(0 <= l);
        assert(l <= r);
        assert(r <= n);
        return cumsum[r] - cumsum[l];
    }
};

#line 2 "datastructure/cumulative_sum.hpp"
#include <vector>
template <typename T>
struct cumulative_sum {
    int n;
    std::vector<T> cumsum;
    cumulative_sum() {
    }
    cumulative_sum(std::vector<T>& d) : n(d.size()), cumsum(n + 1) {
        for (int i = 0; i < n; i++) {
            cumsum[i + 1] = cumsum[i] + d[i];
        }
    }
    T sum(int l, int r) {
        // 0-indexed
        // [l, r)
        assert(0 <= l);
        assert(l <= r);
        assert(r <= n);
        return cumsum[r] - cumsum[l];
    }
};

Back to top page