Persistent Array
(data-structure/persistent_array.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/persistent_array.hpp"

Description

永続配列は，過去のバージョンを保持する配列である．永続配列の要素を変更したとき，変更された値を保持する新しい配列を生成する．

空間計算量: $O(m b \log_b n)$, $m$ は変更の数

Operations

• PersistentArray(vector<T> v)
  • v の要素から永続配列を構築する
  • 時間計算量: $O(nb \log_b n)$
• T get(int k)
  • $k$ 番目の要素を返す
  • 時間計算量: $O(\log_b n)$
• PersistentArray set(int k, T x)
  • $k$ 番目の要素を $x$ に変更した永続配列を返す
  • 時間計算量: $O(b \log_b n)$

Reference

• ゼロから作る永続データ構造

Required by

• Persistent Queue (data-structure/persistent_queue.hpp)
• Persistent Union Find (data-structure/unionfind/persistent_union_find.hpp)

Verified with

• test/yosupo/persistent_queue.test.cpp
• test/yosupo/persistent_unionfind.test.cpp

Code

#pragma once
#include <memory>
#include <vector>

template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};

#line 2 "data-structure/persistent_array.hpp"
#include <memory>
#include <vector>

template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};

Back to top page