Persistent Array (永続配列)
(lib/data_structure/persistent_array.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:54:10+09:00
• Include: #include "lib/data_structure/persistent_array.hpp"

Required by

• Persistent Queue (永続キュー) (lib/data_structure/persistent_queue.hpp)
• Persistent Union Find (永続 UnionFind) (lib/data_structure/persistent_union_find.hpp)

Verified with

• test/library_checker/data_structure/persistent_queue.test.cpp
• test/library_checker/data_structure/persistent_unionfind.test.cpp
• test/library_checker/data_structure/persistent_unionfind_1.test.cpp

Code

#pragma once

/**
 * @brief Persistent Array (永続配列)
 */

#include <cstring>

template<typename T>
struct PersistentArray{
    struct Node{
        T data;
        Node *ch[20] = {};
    };
    Node *root = nullptr;

    PersistentArray() {}

    Node *get_root(){
        return root;
    }

    void destructive_set(const int i, const T &val, Node *&t){
        if(!t) t = new Node();
        if(i == 0){
            t->data = val;
        } else{
            destructive_set(i / 20, val, t->ch[i % 20]);
        }
    }

    Node *set(const int i, const T &val, Node *&t){
        Node *res = new Node();
        if(t){
            std::memcpy(res->ch, t->ch, sizeof(t->ch));
            res->data = t->data;
        }
        if(i == 0){
            res->data = val;
        } else{
            res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
        }
        return res;
    }

    T get(const int i, Node *t){
        if(!t) return T();
        if(i == 0){
            return t->data;
        } else{
            return get(i / 20, t->ch[i % 20]);
        }
    }
};

#line 2 "lib/data_structure/persistent_array.hpp"

/**
 * @brief Persistent Array (永続配列)
 */

#include <cstring>

template<typename T>
struct PersistentArray{
    struct Node{
        T data;
        Node *ch[20] = {};
    };
    Node *root = nullptr;

    PersistentArray() {}

    Node *get_root(){
        return root;
    }

    void destructive_set(const int i, const T &val, Node *&t){
        if(!t) t = new Node();
        if(i == 0){
            t->data = val;
        } else{
            destructive_set(i / 20, val, t->ch[i % 20]);
        }
    }

    Node *set(const int i, const T &val, Node *&t){
        Node *res = new Node();
        if(t){
            std::memcpy(res->ch, t->ch, sizeof(t->ch));
            res->data = t->data;
        }
        if(i == 0){
            res->data = val;
        } else{
            res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
        }
        return res;
    }

    T get(const int i, Node *t){
        if(!t) return T();
        if(i == 0){
            return t->data;
        } else{
            return get(i / 20, t->ch[i % 20]);
        }
    }
};

Back to top page