Src/DataStructure/Set/FenwickSet.hpp

• View this file on GitHub
• Last update: 2025-10-14 12:56:31+09:00
• Include: #include "Src/DataStructure/Set/FenwickSet.hpp"

Depends on

• 加法群 (Src/Algebra/Group/AdditiveGroup.hpp)
• Src/Algebra/Group/GroupConcept.hpp
• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• Fenwick Tree (Src/DataStructure/FenwickTree/FenwickTree.hpp)
• 整数同士の切り捨て/切り上げ除算 (Src/Number/IntegerDivision.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/DataStructure/Set/OfflineOrderedSet.hpp

Verified with

• Test/LC/ordered_set/OfflineOrderedSet.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Number/IntegerDivision.hpp"
#include "../FenwickTree/FenwickTree.hpp"
#include "../../Algebra/Group/AdditiveGroup.hpp"

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

namespace zawa {

class FenwickSet {
public:

    FenwickSet() = default;

    explicit FenwickSet(usize n) 
        : m_n{n}, m_m{DivCeil<usize>(n, 64)}, m_dat(m_m), m_fen(m_m), m_all{} {}

    constexpr usize maxValue() const {
        return m_n;
    }

    usize size() const {
        return m_all;
    }

    void insert(i32 x) {
        assert(0 <= x);
        assert(static_cast<usize>(x) < maxValue());
        if ((m_dat[x / 64] >> (x % 64)) & 1) 
            return;
        m_dat[x / 64] |= u64{1} << (x % 64);
        m_fen.operation(x / 64, 1);
        m_all++;
    }

    void erase(i32 x) {
        assert(static_cast<usize>(x) < maxValue());
        if ((m_dat[x / 64] >> (x % 64)) & 1) {
            m_dat[x / 64] ^= u64{1} << (x % 64);
            m_fen.operation(x / 64, -1);
            m_all--;
        }
    }

    bool contains(i32 x) const {
        assert(static_cast<usize>(x) < maxValue());
        return (m_dat[x / 64] >> (x % 64)) & 1;
    }

    // 1-indexed
    std::optional<usize> kth(i32 k) const {
        assert(k > 0);
        if (static_cast<usize>(k) > m_all) 
            return std::nullopt;
        const usize idx = m_fen.maxRight(0, [&](i32 v) { return v < k; });
        i32 sum = m_fen.prefixProduct(idx);
        assert(sum < k);
        for (usize i = 0 ; i < 64 ; i++)
            if ((m_dat[idx] >> i) & 1) {
                sum++;
                if (sum == k) 
                    return idx * 64 + i;
            }
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

    usize countLessEqual(i32 x) const {
        if (x < 0) 
            return 0;
        if (static_cast<usize>(x) >= maxValue()) 
            return m_all;
        usize sum = m_fen.prefixProduct(x / 64);
        for (i32 i = 0 ; i <= x % 64 ; i++) 
            sum += (m_dat[x / 64] >> i) & 1;
        return sum;
    }

    std::optional<usize> prevEqual(i32 x) const {
        if (countLessEqual(x) == 0) 
            return std::nullopt;
        for (usize i = x % 64 + 1 ; i-- ; ) 
            if ((m_dat[x / 64] >> i) & 1) 
                return (x / 64) * 64 + i;
        const usize idx = m_fen.minLeft(x / 64, [](i32 v) { return v <= 0; });
        for (usize i = 64 ; i-- ; ) 
            if ((m_dat[idx] >> i) & 1)
                return idx * 64 + i;
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

    std::optional<usize> nextEqual(i32 x) const {
        if (m_all == countLessEqual(x - 1))
            return std::nullopt;
        for (usize i = x % 64 ; i < 64 ; i++)
            if ((m_dat[x / 64] >> i) & 1)
                return (x / 64) * 64 + i;
        const usize idx = m_fen.maxRight(x / 64 + 1, [](i32 v) { return v <= 0; });
        for (usize i = 0 ; i < 64 ; i++)
            if ((m_dat[idx] >> i) & 1)
                return idx * 64 + i;
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

private:

    usize m_n{}, m_m{};
    
    std::vector<u64> m_dat;

    FenwickTree<AdditiveGroup<i32>> m_fen;

    usize m_all{0};

};

} // namespace zawa

#line 2 "Src/DataStructure/Set/FenwickSet.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/Number/IntegerDivision.hpp"

#include <type_traits>
#include <cassert>

namespace zawa {

template <class T>
constexpr T DivFloor(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivFloor argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return a / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? a / b : (a - b + 1) / b);
    }
}

template <class T>
constexpr T DivCeil(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivCeil argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return (a + b - 1) / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? (a + b - 1) / b : a / b);
    }
}

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

#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/FenwickTree.hpp"

#include <vector>
#line 8 "Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include <ostream>
#include <functional>
#line 11 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

namespace zawa {

template <concepts::Monoid Monoid>
class FenwickTree {
public:

    using VM = Monoid;
    
    using V = typename VM::Element;

    FenwickTree() = default;

    explicit FenwickTree(usize n) : m_n{ n }, m_bitwidth{ std::__lg(n) + 1 }, m_a(n, VM::identity()), m_dat(n + 1, VM::identity()) {
        m_dat.shrink_to_fit();
        m_a.shrink_to_fit();
    }

    explicit FenwickTree(const std::vector<V>& a) : m_n{ a.size() }, m_bitwidth{ std::__lg(a.size()) + 1 }, m_a(a), m_dat(a.size() + 1, VM::identity()) {
        m_dat.shrink_to_fit();  
        m_a.shrink_to_fit();
        for (i32 i{} ; i < static_cast<i32>(m_n) ; i++) {
            addDat(i, a[i]);
        }
    }

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

    // return a[i]
    const V& get(usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // return a[i]
    const V& operator[](usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // a[i] <- a[i] + v
    void operation(usize i, const V& v) {
        assert(i < size());
        addDat(i, v);
        m_a[i] = VM::operation(m_a[i], v);
    }

    // a[i] <- v
    void assign(usize i, const V& v) requires concepts::Inversible<Monoid> {
        assert(i < size());
        addDat(i, VM::operation(VM::inverse(m_a[i]), v));
        m_a[i] = v;
    }

    // return a[0] + a[1] + ... + a[r - 1]
    V prefixProduct(usize r) const {
        assert(r <= size());
        return product(r);
    }

    // return a[l] + a[l + 1] ... + a[r - 1]
    V product(usize l, usize r) const requires concepts::Inversible<Monoid> {
        assert(l <= r and r <= size());
        return VM::operation(VM::inverse(product(l)), product(r));
    }

    template <class Function>
    usize maxRight(usize l, const Function& f) const requires concepts::Inversible<Monoid> {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "maxRight's argument f must be function bool(T)");
        assert(l <= size());
        assert(f(VM::identity()));
        V sum{ VM::inverse(product(l)) }; 
        usize r{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ r | (1u << bit) };
            if (nxt < m_dat.size() and (nxt <= l or f(VM::operation(sum, m_dat[nxt])))) {
                sum = VM::operation(sum, m_dat[nxt]);
                r = std::move(nxt);
            }
        }
        assert(l <= r);
        return r;
    }

    template <class Function>
    usize minLeft(usize r, const Function& f) const requires concepts::Inversible<Monoid> {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "minLeft's argument f must be function bool(T)");
        assert(r <= size());
        assert(f(VM::identity()));
        V sum{ product(r) };
        usize l{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ l | (1u << bit) };
            if (nxt <= r and not f(VM::operation(VM::inverse(m_dat[nxt]), sum))) {
                sum = VM::operation(VM::inverse(m_dat[nxt]), sum);
                l = std::move(nxt);
            }
        }
        assert(l <= r);
        return l;
    }

    // debug print
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) {
        for (usize i{} ; i <= ft.size() ; i++) {
            os << ft.prefixProduct(i) << (i == ft.size() ? "" : " ");
        }
        return os;
    }

private:

    usize m_n{};

    usize m_bitwidth{};

    std::vector<V> m_a, m_dat;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }
    
    // a[i] <- a[i] + v
    void addDat(i32 i, const V& v) {
        assert(0 <= i and i < static_cast<i32>(m_n));
        for ( i++ ; i < static_cast<i32>(m_dat.size()) ; i += lsb(i)) {
            m_dat[i] = VM::operation(m_dat[i], v);
        }
    }

    // return a[0] + a[1] + .. + a[i - 1]
    V product(i32 i) const {
        assert(0 <= i and i <= static_cast<i32>(m_n));
        V res{ VM::identity() };
        for ( ; i > 0 ; i -= lsb(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

};

} // namespace zawa
#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 7 "Src/DataStructure/Set/FenwickSet.hpp"

#include <bit>
#line 11 "Src/DataStructure/Set/FenwickSet.hpp"
#include <optional>

namespace zawa {

class FenwickSet {
public:

    FenwickSet() = default;

    explicit FenwickSet(usize n) 
        : m_n{n}, m_m{DivCeil<usize>(n, 64)}, m_dat(m_m), m_fen(m_m), m_all{} {}

    constexpr usize maxValue() const {
        return m_n;
    }

    usize size() const {
        return m_all;
    }

    void insert(i32 x) {
        assert(0 <= x);
        assert(static_cast<usize>(x) < maxValue());
        if ((m_dat[x / 64] >> (x % 64)) & 1) 
            return;
        m_dat[x / 64] |= u64{1} << (x % 64);
        m_fen.operation(x / 64, 1);
        m_all++;
    }

    void erase(i32 x) {
        assert(static_cast<usize>(x) < maxValue());
        if ((m_dat[x / 64] >> (x % 64)) & 1) {
            m_dat[x / 64] ^= u64{1} << (x % 64);
            m_fen.operation(x / 64, -1);
            m_all--;
        }
    }

    bool contains(i32 x) const {
        assert(static_cast<usize>(x) < maxValue());
        return (m_dat[x / 64] >> (x % 64)) & 1;
    }

    // 1-indexed
    std::optional<usize> kth(i32 k) const {
        assert(k > 0);
        if (static_cast<usize>(k) > m_all) 
            return std::nullopt;
        const usize idx = m_fen.maxRight(0, [&](i32 v) { return v < k; });
        i32 sum = m_fen.prefixProduct(idx);
        assert(sum < k);
        for (usize i = 0 ; i < 64 ; i++)
            if ((m_dat[idx] >> i) & 1) {
                sum++;
                if (sum == k) 
                    return idx * 64 + i;
            }
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

    usize countLessEqual(i32 x) const {
        if (x < 0) 
            return 0;
        if (static_cast<usize>(x) >= maxValue()) 
            return m_all;
        usize sum = m_fen.prefixProduct(x / 64);
        for (i32 i = 0 ; i <= x % 64 ; i++) 
            sum += (m_dat[x / 64] >> i) & 1;
        return sum;
    }

    std::optional<usize> prevEqual(i32 x) const {
        if (countLessEqual(x) == 0) 
            return std::nullopt;
        for (usize i = x % 64 + 1 ; i-- ; ) 
            if ((m_dat[x / 64] >> i) & 1) 
                return (x / 64) * 64 + i;
        const usize idx = m_fen.minLeft(x / 64, [](i32 v) { return v <= 0; });
        for (usize i = 64 ; i-- ; ) 
            if ((m_dat[idx] >> i) & 1)
                return idx * 64 + i;
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

    std::optional<usize> nextEqual(i32 x) const {
        if (m_all == countLessEqual(x - 1))
            return std::nullopt;
        for (usize i = x % 64 ; i < 64 ; i++)
            if ((m_dat[x / 64] >> i) & 1)
                return (x / 64) * 64 + i;
        const usize idx = m_fen.maxRight(x / 64 + 1, [](i32 v) { return v <= 0; });
        for (usize i = 0 ; i < 64 ; i++)
            if ((m_dat[idx] >> i) & 1)
                return idx * 64 + i;
        assert(!"Fenwick Set library bug");
        return std::nullopt;
    }

private:

    usize m_n{}, m_m{};
    
    std::vector<u64> m_dat;

    FenwickTree<AdditiveGroup<i32>> m_fen;

    usize m_all{0};

};

} // namespace zawa

Back to top page