Dual Sparse Table
(Src/DataStructure/SparseTable/DualSparseTable.hpp)

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

区間更新が何回か来た後、取得クエリがあるようなやつに使える。当然だが、スパーステーブルなので等冪則が成り立つ演算でないと壊れる。

vectorで初期化、operation(l, r, v)で区間更新, buildで全要素取得。

初期化, buildが $O(n\log n)$ 、operationが $O(1)$

Depends on

• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AOJ/2559.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Monoid/MonoidConcept.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <concepts::Monoid S>
class DualSparseTable {
public:
    using Value = typename S::Element;

    DualSparseTable() = default;
    
    DualSparseTable(const std::vector<Value>& A)
        : n_{A.size()}, L_(A.size() + 1), dat_{} {
        
        assert(A.size());
        for (u32 i{1} ; i < L_.size() ; i++) {
            L_[i] = L_[i - 1] + (i >> (L_[i - 1] + 1));
        }
        dat_ = std::vector(L_.back() + 1, std::vector(A.size(), S::identity()));
        dat_[0] = A;
    }

    void operation(u32 L, u32 R, const Value& v) {
        assert(L <= R and R <= size());
        if (L == R) {
            return;
        }
        else if (L + 1 == R) {
            dat_[0][L] = S::operation(dat_[0][L], v);
        }
        else {
            u32 now{L_[R - L]};
            dat_[now][L] = S::operation(dat_[now][L], v);
            dat_[now][R - (1 << now)] = S::operation(dat_[now][R - (1 << now)], v);
        }
    }

    constexpr usize size() const {
        return n_;
    }

    std::vector<Value> build() {
        assert(dat_.size() >= 2u);
        for (u32 i{static_cast<u32>(dat_.size()) - 2u} ; i + 1 < dat_.size() ; i--) {
            for (u32 j{} ; j + (1 << i) < size() ; j++) {
                dat_[i][j] = S::operation(dat_[i][j], dat_[i + 1][j]);
                dat_[i][j + (1 << i)] = S::operation(dat_[i][j + (1 << i)], dat_[i + 1][j]);
            }
        }
        return dat_[0];
    }

private:
    
    usize n_{};
    std::vector<u32> L_;
    std::vector<std::vector<Value>> dat_{};
};

} // namespace zawa

#line 2 "Src/DataStructure/SparseTable/DualSparseTable.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/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 5 "Src/DataStructure/SparseTable/DualSparseTable.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <concepts::Monoid S>
class DualSparseTable {
public:
    using Value = typename S::Element;

    DualSparseTable() = default;
    
    DualSparseTable(const std::vector<Value>& A)
        : n_{A.size()}, L_(A.size() + 1), dat_{} {
        
        assert(A.size());
        for (u32 i{1} ; i < L_.size() ; i++) {
            L_[i] = L_[i - 1] + (i >> (L_[i - 1] + 1));
        }
        dat_ = std::vector(L_.back() + 1, std::vector(A.size(), S::identity()));
        dat_[0] = A;
    }

    void operation(u32 L, u32 R, const Value& v) {
        assert(L <= R and R <= size());
        if (L == R) {
            return;
        }
        else if (L + 1 == R) {
            dat_[0][L] = S::operation(dat_[0][L], v);
        }
        else {
            u32 now{L_[R - L]};
            dat_[now][L] = S::operation(dat_[now][L], v);
            dat_[now][R - (1 << now)] = S::operation(dat_[now][R - (1 << now)], v);
        }
    }

    constexpr usize size() const {
        return n_;
    }

    std::vector<Value> build() {
        assert(dat_.size() >= 2u);
        for (u32 i{static_cast<u32>(dat_.size()) - 2u} ; i + 1 < dat_.size() ; i--) {
            for (u32 j{} ; j + (1 << i) < size() ; j++) {
                dat_[i][j] = S::operation(dat_[i][j], dat_[i + 1][j]);
                dat_[i][j + (1 << i)] = S::operation(dat_[i][j + (1 << i)], dat_[i + 1][j]);
            }
        }
        return dat_[0];
    }

private:
    
    usize n_{};
    std::vector<u32> L_;
    std::vector<std::vector<Value>> dat_{};
};

} // namespace zawa

Back to top page