1次元累積和
(Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp)

View this file on GitHub
Last update: 2023-07-22 13:55:49+09:00
Include: #include "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

概要

群 $(S, \oplus)$ の上で列 $A$ 上のクエリ $\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を処理することができます。ただし、 $A$ に値の変更があってはなりません。

ライブラリの使い方

テンプレート引数Group

以下、テンプレート引数のGroup::ElementをTと略します。

コンストラクタ

(1) PrefixSum1D = default
(2) PrefixSum1D(const std::vector<T>& A)

(1) デフォルトコンストラクタ

(2) $A$ によって累積和 $S$ を構築します。処理する列 $A$ をstd::vector<T>として引数に入れてください。以降、 $A$ の長さを $N$ とします。

計算量: $O(N)$

operator[]

inline T operator[](u32 i) const

$S_i$ を返します。(0-indexedです)

制約: $i\ \le\ N$

計算量: 定数時間

size

inline usize size() const

$S$ の長さを返します。すなわち $N + 1$ です。

計算量: 定数時間

product

T product(u32 l, u32 r) const

$\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を返します。(0-indexedです)

制約: $l\ \le\ r\ \le\ N$

計算量: 定数時間

lowerBound

u32 lowerBound(u32 l, u32 r, const T& v)

$\displaystyle \sum_{i = l}^{r - 1} A_i\ \ge\ v$ となる最左の $r$ を返します。

制約: $l\ \le\ r\ \le\ N$

計算量: $O(r - l)$

upperBound

u32 upperBound(u32 l, u32 r, const T& v)

$\displaystyle \sum_{i = l}^{r - 1} A_i\ > v$ となる最左の $r$ を返します。

制約: $l\ \le\ r\ \le\ N$

計算量: $O(r - l)$

maxRight

u32 maxRight<F>(u32 l, const F& f) const

$S \to \{ \text{true}, \text{false} \}$ でありかつ単調性を持つ関数 $f$ に対して、 $\displaystyle f(\sum_{i = l}^{r - 1} A_i) = \text{false}$ を満たす最左の $r$ を返します。

fは関数オブジェクトを入れる必要があります。(ラムダ式とかstd::function<bool(T)>とかを引数に入れることができる)

制約:

FはT型の値をひとつ引数に取り、bool値を返り値とする関数オブジェクトであること
$e =$ Group::identity()として $f(e) = \text{true}$ を満たすこと
$f$ に副作用が無いこと、あったとしても同じ値を引数に入れたのなら常に同じ結果を返すこと
$l\ \le\ N$

minLeft

未テストでかつ実装に自信が無いです。

u32 minLeft<F>(u32 r, const F& f) const

$S \to \{ \text{true}, \text{false} \}$ でありかつ単調性を持つ関数 $f$ に対して、 $\displaystyle f(\sum_{i = l}^{r - 1} A_i) = \text{false}$ を満たす最右の $l$ を返します。

fは関数オブジェクトを入れる必要があります。(ラムダ式とかstd::function<bool(T)>とかを引数に入れることができる)

制約:

FはT型の値をひとつ引数に取り、bool値を返り値とする関数オブジェクトであること
$e =$ Group::identity()として $f(e) = \text{true}$ を満たすこと
$f$ に副作用が無いこと、あったとしても同じ値を引数に入れたのなら常に同じ結果を返すこと
$l\ \le\ N$

begin

const auto begin() const

内部のコンテナの先頭要素のconst_iteratorを返します。

計算量: 定数時間

end

const auto end() const

内部のコンテナの末尾の次の要素のconst_iteratorを返します。

計算量: 定数時間

アルゴリズム

簡単のため、 $S = \mathbb{Z}$ 、 $\oplus = +$ で考えます。(群の条件を満たすなら他の $(S, \oplus)$ でも勿論なりたちます)

数列 $A$ に対して、 $\displaystyle S_i = A_0 + A_1 + \dots + A_{i - 1} = \sum_{j = 0}^{i - 1} A_{j}$ が成り立つ $S$ を $A$ の累積和(prefix sum、cumulative sum)と呼びます。

例えば、 $A = (1, 3, -2, 4, 3)$ ならば、 $S = (0, 1, 4, 2, 6, 9)$ です。

$\displaystyle \sum_{i = l}^{r - 1} A_i = \sum_{i = 0}^{r - 1} A_i - \sum_{i = 0}^{l - 1} A_i = S_{r} - S_{l}$ が成り立つので、愚直より高速に $\displaystyle \sum_{i = l}^{r - 1} A_i$ を求めることが可能です。

上の例で一つ区間和の例をとると、 $A_1 + A_2 + A_3 = 3 - 2 + 4 = 5, S_{4} - S_{1} = 6 - 1 = 5$ で確かに一致していることがわかります。他の例でも成り立つと思います。

累積和は頭が壊れるので嫌ですね。出るなと念を送りながらコンテストに出ていますが、当然のように毎回出てくるので辛いです。

メモ

可換でない群で累積和を構築する時は注意が必要です。例えば、可換で無い群上で列のSuffix Sumが欲しい時にこのライブラリを貼ると死にます。(product(l, r)の値が異なります)

そもそもそのような実装に注意を払うべきであるような場合は、ライブラリを使うべきでは無いのかも?

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

静的な列上の区間和クエリ (Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp)

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace zawa {

template <class Group>
class PrefixSum1D {
private:
    using T = typename Group::Element;
    std::vector<T> dat_;

    constexpr bool rangeCheck(u32 l, u32 r) const {
        return (l <= r and r < dat_.size());
    }

public:
    PrefixSum1D() = default; 
    PrefixSum1D(const std::vector<T>& A) : dat_(A.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();
        for (u32 i = 0 ; i < A.size() ; i++) {
            dat_[i + 1] = Group::operation(dat_[i], A[i]);
        }
    }

    inline T operator[](u32 i) const {
        assert(i < dat_.size());
        return dat_[i];
    }

    inline usize size() const {
        return dat_.size();
    }

    T product(u32 l, u32 r) const {
        assert(rangeCheck(l, r));
        return Group::operation(Group::inverse(dat_[l]), dat_[r]);
    }

    u32 lowerBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::lower_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    u32 upperBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::upper_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    template <class F>
    u32 maxRight(u32 l, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(l < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(v, Group::inverse(dat_[l])));
        };
        return std::partition_point(dat_.begin() + l, dat_.end(), f_) - dat_.begin();
    }

    template <class F>
    u32 minLeft(u32 r, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(r < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(Group::inverse(v), dat_[r]));
        };
        return dat_.rend() - std::partition_point(dat_.rbegin() + (dat_.size() - r - 1), dat_.rend(), f_) - 1;
    }

    const auto begin() const {
        return dat_.begin();
    }

    const auto end() const {
        return dat_.end();
    }
};

} // namespace zawa

#line 2 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace zawa {

template <class Group>
class PrefixSum1D {
private:
    using T = typename Group::Element;
    std::vector<T> dat_;

    constexpr bool rangeCheck(u32 l, u32 r) const {
        return (l <= r and r < dat_.size());
    }

public:
    PrefixSum1D() = default; 
    PrefixSum1D(const std::vector<T>& A) : dat_(A.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();
        for (u32 i = 0 ; i < A.size() ; i++) {
            dat_[i + 1] = Group::operation(dat_[i], A[i]);
        }
    }

    inline T operator[](u32 i) const {
        assert(i < dat_.size());
        return dat_[i];
    }

    inline usize size() const {
        return dat_.size();
    }

    T product(u32 l, u32 r) const {
        assert(rangeCheck(l, r));
        return Group::operation(Group::inverse(dat_[l]), dat_[r]);
    }

    u32 lowerBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::lower_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    u32 upperBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::upper_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    template <class F>
    u32 maxRight(u32 l, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(l < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(v, Group::inverse(dat_[l])));
        };
        return std::partition_point(dat_.begin() + l, dat_.end(), f_) - dat_.begin();
    }

    template <class F>
    u32 minLeft(u32 r, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(r < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(Group::inverse(v), dat_[r]));
        };
        return dat_.rend() - std::partition_point(dat_.rbegin() + (dat_.size() - r - 1), dat_.rend(), f_) - 1;
    }

    const auto begin() const {
        return dat_.begin();
    }

    const auto end() const {
        return dat_.end();
    }
};

} // namespace zawa

1次元累積和 (Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp)

概要

ライブラリの使い方

テンプレート引数Group

コンストラクタ

operator[]

size

product

lowerBound

upperBound

maxRight

minLeft

begin

end

アルゴリズム

メモ

Depends on

Required by

Verified with

Code

1次元累積和
(Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp)