Persistent Array (data_structure/persistent_array.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-06-22 16:22:13+09:00
• Include: #include "data_structure/persistent_array.hpp"

更新前の状態を保持したまま要素の更新ができる配列です。各更新操作は新しいバージョンの配列を生成します。

使い方

コンストラクタ

PersistentArray(int n)
PersistentArray(int n, T x)
PersistentArray(std::vector<T> v)

説明

指定されたサイズまたは初期値を持つ PersistentArray を構築します。

• n: 配列のサイズ。
• x: 初期値として使用する要素。
• v: 初期値として使用する要素の std::vector。

計算量

$O(N \log N)$ または $O(N)$ (初期化方法による)

set

int set(int p, T v, int t = -1)

説明

指定された位置 p の要素を値 v で更新し、新しいバージョンの配列を生成します。t を指定しない場合、最新のバージョンに対して操作を行います。

• p: 更新する要素のインデックス (0-indexed)。
• v: 設定する値。
• t: 操作を行う配列のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: 新しいバージョンのインデックス。

制約

$0 \le p < N$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

get

T get(int p, int t = -1)

説明

指定されたバージョン t の配列の、位置 p にある要素の値を取得します。t を指定しない場合、最新のバージョンから取得します。

• p: 取得する要素のインデックス (0-indexed)。
• t: 値を取得する配列のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: 指定された位置の要素の値。

制約

$0 \le p < N$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

Required by

• Persistent Union Find (data_structure/persistent_unionfind.hpp)

Verified with

• test/persistent_unionfind.test.cpp

Code

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

template <typename T, auto e = []() { return T(); }>
struct PersistentArray {
    struct node;
    using nptr = std::shared_ptr<node>;
    struct node {
        T v{e()};
        std::array<nptr, 16> c;
        node() {}
        node(T _v) : v(_v) {}
    };
    std::vector<nptr> root;
    int w{0};
    PersistentArray(int n) : PersistentArray(std::vector<T>(n, e())) {}
    PersistentArray(int n, T x) : PersistentArray(std::vector<T>(n, x)) {}
    PersistentArray(std::vector<T> v) : root(1, std::make_shared<node>(node{})) {
        if (v.size() == 1U) {
            root[0] = std::make_shared<node>(node{v[0]});
            return;
        }
        std::vector<nptr> c;
        c.emplace_back(root[0]);
        while (1 << (w + 4) < static_cast<int>(v.size())) {
            w += 4;
            std::vector<nptr> nxt;
            for (auto &p : c) {
                for (int i = 0; i < 16; ++i) {
                    p->c[i] = std::make_shared<node>(node{});
                    nxt.emplace_back(p->c[i]);
                }
            }
            std::swap(c, nxt);
        }
        {
            w += 4;
            uint sum = 0;
            for (auto &p : c) {
                for (uint i = 0; i < 16; ++i) {
                    if (v.size() <= sum + i) break;
                    p->c[i] = std::make_shared<node>(node{v[sum + i]});
                }
                sum += 16U;
            }
        }
    }

    int set(int p, T v, int t = -1) {
        if (t == -1) {
            t = static_cast<int>(root.size()) - 1;
        }
        root.emplace_back(std::make_shared<node>(*root[t]));
        set(root.back(), p, v, w);
        return static_cast<int>(root.size()) - 1;
    }
    void set(nptr &ptr, int p, T v, int w) {
        if (w == 0) {
            ptr->v = v;
            return;
        }
        w -= 4;
        ptr->c[p >> w] = std::make_shared<node>(*(ptr->c[p >> w]));
        set(ptr->c[p >> w], p & ((1 << w) - 1), v, w);
    }

    T get(int p, int t = -1) {
        if (t == -1) {
            t = static_cast<int>(root.size()) - 1;
        }
        return get(root[t], p, w);
    }
    T get(const nptr &ptr, int p, int w) {
        if (w == 0) {
            return ptr->v;
        }
        w -= 4;
        return get(ptr->c[p >> w], p & ((1 << w) - 1), w);
    }
};

#line 2 "data_structure/persistent_array.hpp"
#include <array>
#include <memory>
#include <vector>

template <typename T, auto e = []() { return T(); }>
struct PersistentArray {
    struct node;
    using nptr = std::shared_ptr<node>;
    struct node {
        T v{e()};
        std::array<nptr, 16> c;
        node() {}
        node(T _v) : v(_v) {}
    };
    std::vector<nptr> root;
    int w{0};
    PersistentArray(int n) : PersistentArray(std::vector<T>(n, e())) {}
    PersistentArray(int n, T x) : PersistentArray(std::vector<T>(n, x)) {}
    PersistentArray(std::vector<T> v) : root(1, std::make_shared<node>(node{})) {
        if (v.size() == 1U) {
            root[0] = std::make_shared<node>(node{v[0]});
            return;
        }
        std::vector<nptr> c;
        c.emplace_back(root[0]);
        while (1 << (w + 4) < static_cast<int>(v.size())) {
            w += 4;
            std::vector<nptr> nxt;
            for (auto &p : c) {
                for (int i = 0; i < 16; ++i) {
                    p->c[i] = std::make_shared<node>(node{});
                    nxt.emplace_back(p->c[i]);
                }
            }
            std::swap(c, nxt);
        }
        {
            w += 4;
            uint sum = 0;
            for (auto &p : c) {
                for (uint i = 0; i < 16; ++i) {
                    if (v.size() <= sum + i) break;
                    p->c[i] = std::make_shared<node>(node{v[sum + i]});
                }
                sum += 16U;
            }
        }
    }

    int set(int p, T v, int t = -1) {
        if (t == -1) {
            t = static_cast<int>(root.size()) - 1;
        }
        root.emplace_back(std::make_shared<node>(*root[t]));
        set(root.back(), p, v, w);
        return static_cast<int>(root.size()) - 1;
    }
    void set(nptr &ptr, int p, T v, int w) {
        if (w == 0) {
            ptr->v = v;
            return;
        }
        w -= 4;
        ptr->c[p >> w] = std::make_shared<node>(*(ptr->c[p >> w]));
        set(ptr->c[p >> w], p & ((1 << w) - 1), v, w);
    }

    T get(int p, int t = -1) {
        if (t == -1) {
            t = static_cast<int>(root.size()) - 1;
        }
        return get(root[t], p, w);
    }
    T get(const nptr &ptr, int p, int w) {
        if (w == 0) {
            return ptr->v;
        }
        w -= 4;
        return get(ptr->c[p >> w], p & ((1 << w) - 1), w);
    }
};

Back to top page