Src/DataStructure/PrefixSum/PrefixSum2D.hpp

View this file on GitHub
Last update: 2025-12-23 18:04:55+09:00
Include: #include "Src/DataStructure/PrefixSum/PrefixSum2D.hpp"

Depends on

Verified with

Code

#pragma once

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

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

namespace internal {

template <concepts::Group G>
class StaticRectSumSolver {
public:
    
    using T = typename G::Element;

    using const_iterator = typename std::vector<std::vector<T>>::const_iterator;

    explicit StaticRectSumSolver(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum(m_H + 1, std::vector<T>(m_W + 1, G::identity())) {
        for (usize i = 0 ; i < m_H ; i++)
            for (usize j = 0 ; j < m_W ; j++)
                m_sum[i + 1][j + 1] = G::operation(
                        G::operation(m_sum[i + 1][j], m_sum[i][j + 1]), 
                        G::operation(G::inverse(m_sum[i][j]), a[i][j])
                        );
    }

    explicit StaticRectSumSolver(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum{std::move(a)} {
        for (usize i = 0 ; i < m_H ; i++)
            m_sum[i].push_back(G::identity());
        m_sum.push_back(std::vector<T>(m_W + 1, G::identity()));
        for (usize i = 0 ; i <= m_H ; i++)
            for (usize j = m_W ; j-- ; )
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i][j + 1]);
        for (usize i = m_H ; i-- ; )
            for (usize j = 0 ; j <= m_W ; j++)
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i + 1][j]);
    }

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    // [l, r) x [d, u)
    T product(usize l, usize d, usize r, usize u) const {
        assert((l <= r and r <= height()) and "invalid i range: StaticRectSumSolver::product");
        assert((d <= u and u <= width()) and "invalid j range: StaticRectSumSolver::product");
        return G::operation(
                G::operation(m_sum[r][u], m_sum[l][d]),
                G::inverse(G::operation(m_sum[r][d], m_sum[l][u]))
                );
    }

    const std::vector<T>& operator[](usize i) const {
        assert(i <= height() and "invalid access m_sum[i]: StaticRectSumSolver::operator[]");
        return m_sum[i];
    }

    const_iterator begin() const {
        return m_sum.begin();
    }
    
    const_iterator end() const {
        return m_sum.end();
    }

private:

    usize m_H, m_W;

    std::vector<std::vector<T>> m_sum;
};

} // namespace internal

template <concepts::Group G>
class Ruisekiwa2D {
public:
    
    using T = typename G::Element;

    Ruisekiwa2D(usize H, usize W) : m_H{H}, m_W{W}, m_a(H, std::vector<T>(W, G::identity())) {}

    explicit Ruisekiwa2D(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{std::move(a)} {}

    explicit Ruisekiwa2D(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{a} {}

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    void operation(usize i, usize j, T v) {
        assert((i < height() and j < width()) and "invalid range: Ruisekiwa2D::operation");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operation");
        m_a[i][j] = G::operation(m_a[i][j], v);
    }

    const std::vector<T>& operator[](const usize i) const {
        assert(i < height() and "invalid range: Ruisekiwa2D::operator[]");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operator[]");
        return m_a[i];
    }

    internal::StaticRectSumSolver<G> build() const {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        return internal::StaticRectSumSolver<G>{m_a};
    }

    internal::StaticRectSumSolver<G> inplaceBuild() {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        m_moved = true;
        return internal::StaticRectSumSolver<G>{std::move(m_a)};
    }

private:

    usize m_H = 0, m_W = 0;

    std::vector<std::vector<T>> m_a;

    bool m_moved = false;
};

} // namespace zawa

#line 2 "Src/DataStructure/PrefixSum/PrefixSum2D.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/PrefixSum/PrefixSum2D.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

namespace internal {

template <concepts::Group G>
class StaticRectSumSolver {
public:
    
    using T = typename G::Element;

    using const_iterator = typename std::vector<std::vector<T>>::const_iterator;

    explicit StaticRectSumSolver(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum(m_H + 1, std::vector<T>(m_W + 1, G::identity())) {
        for (usize i = 0 ; i < m_H ; i++)
            for (usize j = 0 ; j < m_W ; j++)
                m_sum[i + 1][j + 1] = G::operation(
                        G::operation(m_sum[i + 1][j], m_sum[i][j + 1]), 
                        G::operation(G::inverse(m_sum[i][j]), a[i][j])
                        );
    }

    explicit StaticRectSumSolver(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum{std::move(a)} {
        for (usize i = 0 ; i < m_H ; i++)
            m_sum[i].push_back(G::identity());
        m_sum.push_back(std::vector<T>(m_W + 1, G::identity()));
        for (usize i = 0 ; i <= m_H ; i++)
            for (usize j = m_W ; j-- ; )
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i][j + 1]);
        for (usize i = m_H ; i-- ; )
            for (usize j = 0 ; j <= m_W ; j++)
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i + 1][j]);
    }

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    // [l, r) x [d, u)
    T product(usize l, usize d, usize r, usize u) const {
        assert((l <= r and r <= height()) and "invalid i range: StaticRectSumSolver::product");
        assert((d <= u and u <= width()) and "invalid j range: StaticRectSumSolver::product");
        return G::operation(
                G::operation(m_sum[r][u], m_sum[l][d]),
                G::inverse(G::operation(m_sum[r][d], m_sum[l][u]))
                );
    }

    const std::vector<T>& operator[](usize i) const {
        assert(i <= height() and "invalid access m_sum[i]: StaticRectSumSolver::operator[]");
        return m_sum[i];
    }

    const_iterator begin() const {
        return m_sum.begin();
    }
    
    const_iterator end() const {
        return m_sum.end();
    }

private:

    usize m_H, m_W;

    std::vector<std::vector<T>> m_sum;
};

} // namespace internal

template <concepts::Group G>
class Ruisekiwa2D {
public:
    
    using T = typename G::Element;

    Ruisekiwa2D(usize H, usize W) : m_H{H}, m_W{W}, m_a(H, std::vector<T>(W, G::identity())) {}

    explicit Ruisekiwa2D(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{std::move(a)} {}

    explicit Ruisekiwa2D(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{a} {}

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    void operation(usize i, usize j, T v) {
        assert((i < height() and j < width()) and "invalid range: Ruisekiwa2D::operation");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operation");
        m_a[i][j] = G::operation(m_a[i][j], v);
    }

    const std::vector<T>& operator[](const usize i) const {
        assert(i < height() and "invalid range: Ruisekiwa2D::operator[]");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operator[]");
        return m_a[i];
    }

    internal::StaticRectSumSolver<G> build() const {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        return internal::StaticRectSumSolver<G>{m_a};
    }

    internal::StaticRectSumSolver<G> inplaceBuild() {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        m_moved = true;
        return internal::StaticRectSumSolver<G>{std::move(m_a)};
    }

private:

    usize m_H = 0, m_W = 0;

    std::vector<std::vector<T>> m_a;

    bool m_moved = false;
};

} // namespace zawa