Cartesian Tree
(Src/Sequence/CartesianTree.hpp)

• View this file on GitHub
• Last update: 2024-11-14 17:39:23+09:00
• Include: #include "Src/Sequence/CartesianTree.hpp"

概要

数列に対して「最大値/最小値を境界に高々２つの区間に分ける」という操作の過程を木で表したものを構築する。

最大値・最小値で分ける分割統治と相性が良い。

ライブラリの使い方

template <class F>
requires std::strict_weak_order<F, T, T>
CartesianTree(const std::vector<T>& A, F comp)

compはTに関する狭義の弱順序、$comp :T\times T\rightarrow \text{bool}$ である必要がある。

Depends on

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

Verified with

• Test/AOJ/DPL_3_C.test.cpp
• Test/LC/cartesian_tree.test.cpp

Code

#pragma once

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

#include <concepts>
#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

template <class T>
class CartesianTree {
public:

    static constexpr usize Invalid{static_cast<usize>(-1)};

    struct Node {
        usize left{Invalid}, right{Invalid}, par{Invalid}, idx{Invalid};
        T value{};
        std::vector<usize> childs() const noexcept {
            std::vector<usize> res;
            res.reserve(2);
            if (left != Invalid) res.push_back(left);
            if (right != Invalid) res.push_back(right);
            return res;
        }
        usize countChilds() const noexcept {
            return (left != Invalid) + (right != Invalid);
        }
    };

    CartesianTree() = default;

    template <class F>
    requires std::strict_weak_order<F, T, T>
    CartesianTree(const std::vector<T>& A, F comp) 
        : m_size{A.size()}, m_nodes(A.size()) {

        std::vector<usize> stack(A.size());
        usize top{};
        for (usize i{} ; i < size() ; i++) {
            if (top and comp(A[i], A[stack[top - 1]])) {
                while (top and comp(A[i], A[stack[top - 1]])) top--;
                m_nodes[i].left = stack[top];
                m_nodes[stack[top]].par = i;
            }
            if (top) {
                m_nodes[i].par = stack[top - 1];
                m_nodes[stack[top - 1]].right = i;
            }
            else {
                m_root = i;
            }
            m_nodes[i].value = A[i];
            m_nodes[i].idx = i;
            stack[top++] = i;
        }
    }

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

    inline usize root() const noexcept {
        return m_root;
    }

    inline T value(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].value;
    }

    inline usize parent(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].par;
    }

    inline usize left(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].left;
    }

    inline usize right(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].right;
    }

    template <class F>
    void treeDP(F func) {
        static_assert(std::is_invocable_v<F, const Node&>, "F must be invocable f(const Node&)");
        dfs(m_root, func);
    }

private:

    template <class F>
    void dfs(usize v, F func) {
        if (m_nodes[v].left != Invalid) dfs(m_nodes[v].left, func);
        if (m_nodes[v].right != Invalid) dfs(m_nodes[v].right, func);
        func(m_nodes[v]);
    }

    usize m_size{}, m_root{Invalid};
    std::vector<Node> m_nodes;
};

} // namespace zawa

#line 2 "Src/Sequence/CartesianTree.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/Sequence/CartesianTree.hpp"

#include <concepts>
#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

template <class T>
class CartesianTree {
public:

    static constexpr usize Invalid{static_cast<usize>(-1)};

    struct Node {
        usize left{Invalid}, right{Invalid}, par{Invalid}, idx{Invalid};
        T value{};
        std::vector<usize> childs() const noexcept {
            std::vector<usize> res;
            res.reserve(2);
            if (left != Invalid) res.push_back(left);
            if (right != Invalid) res.push_back(right);
            return res;
        }
        usize countChilds() const noexcept {
            return (left != Invalid) + (right != Invalid);
        }
    };

    CartesianTree() = default;

    template <class F>
    requires std::strict_weak_order<F, T, T>
    CartesianTree(const std::vector<T>& A, F comp) 
        : m_size{A.size()}, m_nodes(A.size()) {

        std::vector<usize> stack(A.size());
        usize top{};
        for (usize i{} ; i < size() ; i++) {
            if (top and comp(A[i], A[stack[top - 1]])) {
                while (top and comp(A[i], A[stack[top - 1]])) top--;
                m_nodes[i].left = stack[top];
                m_nodes[stack[top]].par = i;
            }
            if (top) {
                m_nodes[i].par = stack[top - 1];
                m_nodes[stack[top - 1]].right = i;
            }
            else {
                m_root = i;
            }
            m_nodes[i].value = A[i];
            m_nodes[i].idx = i;
            stack[top++] = i;
        }
    }

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

    inline usize root() const noexcept {
        return m_root;
    }

    inline T value(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].value;
    }

    inline usize parent(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].par;
    }

    inline usize left(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].left;
    }

    inline usize right(usize i) const noexcept {
        assert(i < size());
        return m_nodes[i].right;
    }

    template <class F>
    void treeDP(F func) {
        static_assert(std::is_invocable_v<F, const Node&>, "F must be invocable f(const Node&)");
        dfs(m_root, func);
    }

private:

    template <class F>
    void dfs(usize v, F func) {
        if (m_nodes[v].left != Invalid) dfs(m_nodes[v].left, func);
        if (m_nodes[v].right != Invalid) dfs(m_nodes[v].right, func);
        func(m_nodes[v]);
    }

    usize m_size{}, m_root{Invalid};
    std::vector<Node> m_nodes;
};

} // namespace zawa

Back to top page