Dual Fenwick Tree
(Src/DataStructure/FenwickTree/DualFenwickTree.hpp)

View this file on GitHub
Last update: 2025-04-17 19:44:48+09:00
Include: #include "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"

概要

可換群 $G = (S, \circ)$ 上で列上の区間加算、一点取得クエリに答えることができるデータ構造です。

以後、管理する列を $A$ とします。

ライブラリの使い方

テンプレート引数

template <Concept::Group G>

いつもの。雛形は以下から

class G {
public:
    using Element = ;
    static T identity() noexcept {
    }
    static T operation(const T& l, const T& r) noexcept {
    }
    static T inverse(const T& v) noexcept {
    }
};

以下、G::ElementをVと略す。

コンストラクタ

(1) FenwickTree()
(2) FenwickTree(usize n)
(3) FenwickTree(const std::vector<V>& d)
(4) FenwickTree<std::input_iterator It>(It first, It last)

(2) $A$ を長さ $n$ で各要素が Group::identity である列で初期化します

計算量: $O(n)$

(3) $A$ を d で初期化します

計算量: dの長さを $n$ として $O(n\log n)$

(4) $A$ をiterator範囲[first, last)で初期化します。

計算量: std::distance(first, last)を $n$ として $O(n\log n)$

get, operator[]

V operator[](usize i) const

$A_i$ を返します。

制約: $0\ \le\ i\ <\ n$

計算量: $O(\log n)$

size

usize size() const noexcept

$A$ の要素数を返します。

計算量: 定数時間

operation

void operation(usize i, const Value& v) (1)
void operation(usize l, usize r, const Value& v) (2)

(1) $A_i$ を $A_i \circ v$ に置き換えます。

制約: $0\ \le\ i\ <\ n$

計算量: $O(\log n)$

(2) $A_{l}, A_{l+1}, \dots, A_{r - 1}$ にそれぞれ $v$ を加算する。

制約: $0\ \le\ l\ \le r\ \le n$

計算量: $O(\log n)$

set

void set(usize i, const Value& v)

$A_i$ を $v$ を置き換えます。

制約: $0\ \le\ i\ <\ n$

計算量: $O(\log n)$

maxRight

template <class F>
requires Concept::Predicate<F, V>
std::optional<usize> maxRight(usize l, F f) const

ある$l$ 以上の整数 $m$ が存在して、 $l$ 以上 $m$ 未満の整数 $i$ について $\displaystyle f(A_{j}) = \text{true}$ かつ $m$ 以上の整数 $i$ について $f(A_{j}) = \text{false}$ であることを仮定します。

そのような状況で、 $m$ を発見して返します。

ただし、 $f(\displaystyle \prod_{i = l}^{n - 1} A_{i}) = \text{true}$ の時は std::nullopt を返します。

制約

$0\ \le\ l\ <\ n$
f はV型の変数vに対してf(v)と関数呼び出し可能であり、その返り値がbool型である。
fは上記の仮定を満たす

計算量: $O(\log n)$

Depends on

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Group/GroupConcept.hpp"

#include <bit>
#include <cassert>
#include <concepts>
#include <iterator>
#include <optional>
#include <vector>

namespace zawa {

namespace concepts {

template <class F, class V>
concept Predicate = requires {
    { std::declval<F>()(std::declval<V>()) } -> std::same_as<bool>; 
};

} // namespace Concept

template <concepts::Group G>
class DualFenwickTree {
public:

    using V = typename G::Element;

    constexpr static u32 Log2(usize n) noexcept {
        return static_cast<u32>(
                    std::bit_width(n) - (std::has_single_bit(n) ? 1 : 0)
                );
    }

    DualFenwickTree() = default;

    DualFenwickTree(usize n) : n_{n}, lg_{Log2(n)}, dat_(n+1, G::identity()) {
        assert(n);
    }

    DualFenwickTree(const std::vector<V>& d) : n_{d.size()}, lg_{Log2(n_)}, dat_(d.size() + 1, G::identity()) {
        assert(d.size());
        add(0, d[0]);
        for (usize i = 1 ; i < d.size() ; i++) add(i, G::operation(G::inverse(d[i - 1]), d[i]));
    }

    template <std::input_iterator It>
    DualFenwickTree(It first, It last) 
    : n_{static_cast<usize>(std::distance(first, last))}, lg_{Log2(n_)}, dat_(n_ + 1, G::identity()) {
        assert(first != last);
        V pv = static_cast<V>(*first);
        add(0, pv);
        for (usize i = 1 ; i < n_ ; i++) {
            first++;
            V v = static_cast<V>(*first);
            add(i, G::operation(G::inverse(pv), v));
            pv = v;
        } 
    }

    inline usize size() const noexcept {
        return n_;
    }

    void operation(usize l, usize r, const V& v) {
        assert(l <= r and r <= size());
        if (l < r) {
            add(l, v);
            if (r < size()) add(r, G::inverse(v));
        }
    }

    void operation(usize i, const V& v) {
        assert(i < size());
        operation(i, i + 1, v);
    }

    V operator[](i32 i) const {
        assert(0 <= i and i < (i32)size());
        V res = G::identity();
        for (i++ ; i ; i -= lsb(i)) res = G::operation(dat_[i], res);
        return res;
    }

    void set(usize i, V v) {
        assert(0 <= i and i < size());
        v = G::operation(G::inverse((*this)[i]), v);
        operation(i, v);
    }

    template <class F>
    std::optional<usize> maxRight(usize l, F f) const requires concepts::Predicate<F, V> {
        assert(l < size());
        V sum = l ? (*this)[l - 1] : G::identity();
        usize r = 0;
        for (u32 w = lg_ ; w <= lg_ ; w--) {
            usize next = r | (1u << w);
            if (next >= dat_.size()) continue;
            V nsum = G::operation(sum, dat_[next]);
            if (f(nsum)) {
                sum = std::move(nsum);
                r = std::move(next);
            }
        }
        assert(l <= r);
        return r == size() and f(sum) ? std::nullopt : std::optional{r};
    }

    // 実装が合いません。頭が悪いので
    // template <class F>
    // requires Concept::Predicate<F, V>
    // std::optional<usize> minLeft(usize r, F f) const {
    //     assert(r <= n_);
    //     V sum = G::identity();
    //     usize l = 0;
    //     for (u32 w = lg_ ; w <= lg_ ; w--) {
    //         u32 next = l | (1u << w);
    //         if (next >= r) continue;
    //         V nsum = G::operation(dat_[next], sum);
    //         if (!f(nsum)) {
    //             sum = std::move(nsum);
    //             l = std::move(next);
    //         }
    //     }
    //     assert(l <= r);
    //     if (l + 1 == r and !f(sum)) return r;
    //     return l == 0u and f(sum) ? std::nullopt : std::optional{l};
    // }

private:

    usize n_;

    u32 lg_;

    std::vector<V> dat_;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }

    void add(i32 i, const V& v) {
        for (i++ ; i <= (i32)size() ; i += lsb(i)) dat_[i] = G::operation(dat_[i], v);
    }
};

} // namespace zawa

#line 2 "Src/DataStructure/FenwickTree/DualFenwickTree.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 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"

#include <bit>
#include <cassert>
#line 9 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"
#include <iterator>
#include <optional>
#include <vector>

namespace zawa {

namespace concepts {

template <class F, class V>
concept Predicate = requires {
    { std::declval<F>()(std::declval<V>()) } -> std::same_as<bool>; 
};

} // namespace Concept

template <concepts::Group G>
class DualFenwickTree {
public:

    using V = typename G::Element;

    constexpr static u32 Log2(usize n) noexcept {
        return static_cast<u32>(
                    std::bit_width(n) - (std::has_single_bit(n) ? 1 : 0)
                );
    }

    DualFenwickTree() = default;

    DualFenwickTree(usize n) : n_{n}, lg_{Log2(n)}, dat_(n+1, G::identity()) {
        assert(n);
    }

    DualFenwickTree(const std::vector<V>& d) : n_{d.size()}, lg_{Log2(n_)}, dat_(d.size() + 1, G::identity()) {
        assert(d.size());
        add(0, d[0]);
        for (usize i = 1 ; i < d.size() ; i++) add(i, G::operation(G::inverse(d[i - 1]), d[i]));
    }

    template <std::input_iterator It>
    DualFenwickTree(It first, It last) 
    : n_{static_cast<usize>(std::distance(first, last))}, lg_{Log2(n_)}, dat_(n_ + 1, G::identity()) {
        assert(first != last);
        V pv = static_cast<V>(*first);
        add(0, pv);
        for (usize i = 1 ; i < n_ ; i++) {
            first++;
            V v = static_cast<V>(*first);
            add(i, G::operation(G::inverse(pv), v));
            pv = v;
        } 
    }

    inline usize size() const noexcept {
        return n_;
    }

    void operation(usize l, usize r, const V& v) {
        assert(l <= r and r <= size());
        if (l < r) {
            add(l, v);
            if (r < size()) add(r, G::inverse(v));
        }
    }

    void operation(usize i, const V& v) {
        assert(i < size());
        operation(i, i + 1, v);
    }

    V operator[](i32 i) const {
        assert(0 <= i and i < (i32)size());
        V res = G::identity();
        for (i++ ; i ; i -= lsb(i)) res = G::operation(dat_[i], res);
        return res;
    }

    void set(usize i, V v) {
        assert(0 <= i and i < size());
        v = G::operation(G::inverse((*this)[i]), v);
        operation(i, v);
    }

    template <class F>
    std::optional<usize> maxRight(usize l, F f) const requires concepts::Predicate<F, V> {
        assert(l < size());
        V sum = l ? (*this)[l - 1] : G::identity();
        usize r = 0;
        for (u32 w = lg_ ; w <= lg_ ; w--) {
            usize next = r | (1u << w);
            if (next >= dat_.size()) continue;
            V nsum = G::operation(sum, dat_[next]);
            if (f(nsum)) {
                sum = std::move(nsum);
                r = std::move(next);
            }
        }
        assert(l <= r);
        return r == size() and f(sum) ? std::nullopt : std::optional{r};
    }

    // 実装が合いません。頭が悪いので
    // template <class F>
    // requires Concept::Predicate<F, V>
    // std::optional<usize> minLeft(usize r, F f) const {
    //     assert(r <= n_);
    //     V sum = G::identity();
    //     usize l = 0;
    //     for (u32 w = lg_ ; w <= lg_ ; w--) {
    //         u32 next = l | (1u << w);
    //         if (next >= r) continue;
    //         V nsum = G::operation(dat_[next], sum);
    //         if (!f(nsum)) {
    //             sum = std::move(nsum);
    //             l = std::move(next);
    //         }
    //     }
    //     assert(l <= r);
    //     if (l + 1 == r and !f(sum)) return r;
    //     return l == 0u and f(sum) ? std::nullopt : std::optional{l};
    // }

private:

    usize n_;

    u32 lg_;

    std::vector<V> dat_;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }

    void add(i32 i, const V& v) {
        for (i++ ; i <= (i32)size() ; i += lsb(i)) dat_[i] = G::operation(dat_[i], v);
    }
};

} // namespace zawa

Dual Fenwick Tree (Src/DataStructure/FenwickTree/DualFenwickTree.hpp)

概要

ライブラリの使い方

テンプレート引数

コンストラクタ

get, operator[]

size

operation

set

maxRight

Depends on

Verified with

Code

Dual Fenwick Tree
(Src/DataStructure/FenwickTree/DualFenwickTree.hpp)