Persistent Array
(DataStructure/persistentarray.hpp)

• View this file on GitHub
• Last update: 2022-01-16 22:20:31+09:00
• Include: #include "DataStructure/persistentarray.hpp"

Required by

• Persistent Union Find (DataStructure/persistentunionfind.hpp)

Verified with

• Verify/LC_persistent_unionfind.test.cpp

Code

#pragma once

template<typename T,int B=4>class PersistentArray{
    const int M=(1<<B)-1;
    struct Node{
        Node *cp[1<<B]={};
        T val;
    };
    Node* set(int i,T x,Node* a){
        Node *ret=new Node();
        if(a){
            memcpy(ret->cp,a->cp,sizeof(a->cp));
            ret->val=a->val;
        }
        if(i)ret->cp[i&M]=set(i>>B,x,ret->cp[i&M]);
        else ret->val=x;
        return ret;
    }
    T get(int i,Node* a){
        if(i)return get(i>>B,a->cp[i&M]);
        else return a->val;
    }
public:
    Node *root;
    PersistentArray(Node* _r=nullptr):root(_r){}
    void set(int i,T x){
        root=set(i,x,root);
    }
    T get(int i){
        return get(i,root);
    }
};

/**
 * @brief Persistent Array
 */

#line 2 "DataStructure/persistentarray.hpp"

template<typename T,int B=4>class PersistentArray{
    const int M=(1<<B)-1;
    struct Node{
        Node *cp[1<<B]={};
        T val;
    };
    Node* set(int i,T x,Node* a){
        Node *ret=new Node();
        if(a){
            memcpy(ret->cp,a->cp,sizeof(a->cp));
            ret->val=a->val;
        }
        if(i)ret->cp[i&M]=set(i>>B,x,ret->cp[i&M]);
        else ret->val=x;
        return ret;
    }
    T get(int i,Node* a){
        if(i)return get(i>>B,a->cp[i&M]);
        else return a->val;
    }
public:
    Node *root;
    PersistentArray(Node* _r=nullptr):root(_r){}
    void set(int i,T x){
        root=set(i,x,root);
    }
    T get(int i){
        return get(i,root);
    }
};

/**
 * @brief Persistent Array
 */

Back to top page