cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: Persistent Fenwick Tree
(library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp)

Persistent Fenwick Tree

Fenwick Tree の値を二分木における in-order で配置すると，add, sum の操作が根から (葉とは限らない) ある節点までのパス上で完結する．即ち，Segment Tree 等と同様にして永続化することが出来る．

永続セグメント木よりも定数倍がよいか?

例. Rectangle Sum での速度比較

Depends on

Verified with

Code

#ifndef SUISEN_PERSISTENT_FENWICK_TREE
#define SUISEN_PERSISTENT_FENWICK_TREE

#include <cassert>

#include "library/util/object_pool.hpp"

namespace suisen {
    template <typename T>
    struct PersistentFenwickTree {
        struct Node;

        using value_type = T;

        using node_type = Node;
        using node_pointer_type = node_type*;

        struct Node {
            static inline ObjectPool<node_type> _pool;

            node_pointer_type _ch[2]{ nullptr, nullptr };
            value_type _dat;

            Node() : _dat{} {}

            static node_pointer_type clone(node_pointer_type node) {
                return &(*_pool.alloc() = *node);
            }

            static node_pointer_type build(const std::vector<value_type> &dat, int p) {
                const int n = dat.size();
                std::vector<node_pointer_type> nodes(n + 1);
                auto rec = [&](auto rec, int p, int id) -> node_pointer_type {
                    if (p == 0) return nullptr;
                    const int np = p >> 1;
                    node_pointer_type res = _pool.alloc();
                    res->_ch[0] = rec(rec, np, id - np);
                    if (id + 1 <= n) res->_ch[1] = rec(rec, np, id + np);
                    if (id <= n) nodes[id] = res;
                    return res;
                };
                node_pointer_type res = rec(rec, p, p);
                for (int i = 1; i <= n; ++i) {
                    int par = i + (i & -i);
                    if (par <= n) nodes[par]->_dat += nodes[i]->_dat;
                }
                return res;
            }

            static value_type sum(node_pointer_type node, int p, int l, int r) {
                return sum(node, p, r) - sum(node, p, l);
            }

            static node_pointer_type add(node_pointer_type node, int p, int i, const value_type& val) {
                ++i;
                node_pointer_type res = clone(node);
                for (node_pointer_type cur = res;; p >>= 1) {
                    if (i & p) {
                        if (i ^= p) {
                            cur = cur->_ch[1] = clone(cur->_ch[1]);
                        } else {
                            cur->_dat += val;
                            return res;
                        }
                    } else {
                        cur->_dat += val;
                        cur = cur->_ch[0] = clone(cur->_ch[0]);
                    }
                }
            }
        private:
            static value_type sum(node_pointer_type node, int p, int r) {
                value_type res{};
                for (; r; p >>= 1) {
                    if (r & p) {
                        r ^= p;
                        res += node->_dat;
                        node = node->_ch[1];
                    } else {
                        node = node->_ch[0];
                    }
                }
                return res;
            }
        };

        PersistentFenwickTree() : _p(0), _root(nullptr) {}
        explicit PersistentFenwickTree(int n) : PersistentFenwickTree(std::vector<value_type>(n, T{})) {}
        PersistentFenwickTree(const std::vector<value_type>& dat) : _p(floor_pow2(dat.size())), _root(node_type::build(dat, _p)) {}

        static void init_pool(int size) {
            node_type::_pool = ObjectPool<node_type>(size);
        }
        static void clear_pool() {
            node_type::_pool.clear();
        }

        value_type sum(int l, int r) {
            return node_type::sum(_root, _p, l, r);
        }
        PersistentFenwickTree add(int i, const value_type &val) {
            return PersistentFenwickTree(_p, node_type::add(_root, _p, i, val));
        }

    private:
        int _p;
        node_pointer_type _root;
        PersistentFenwickTree(int p, node_pointer_type root) : _p(p), _root(root) {}

        static constexpr int floor_pow2(int n) {
            int x = 31 - __builtin_clz(n);
            return x < 0 ? 0 : 1 << x;
        }
    };
}

#endif // SUISEN_PERSISTENT_FENWICK_TREE
#line 1 "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"



#include <cassert>

#line 1 "library/util/object_pool.hpp"



#include <deque>
#include <vector>

namespace suisen {
    template <typename T, bool auto_extend = false>
    struct ObjectPool {
        using value_type = T;
        using value_pointer_type = T*;

        template <typename U>
        using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;

        container_type<value_type> pool;
        container_type<value_pointer_type> stock;
        decltype(stock.begin()) it;

        ObjectPool() : ObjectPool(0) {}
        ObjectPool(int size) : pool(size), stock(size) {
            clear();
        }

        int capacity() const { return pool.size(); }
        int size() const { return it - stock.begin(); }

        value_pointer_type alloc() {
            if constexpr (auto_extend) ensure();
            return *it++;
        }

        void free(value_pointer_type t) {
            *--it = t;
        }

        void clear() {
            int size = pool.size();
            it = stock.begin();
            for (int i = 0; i < size; i++) stock[i] = &pool[i];
        }

        void ensure() {
            if (it != stock.end()) return;
            int size = stock.size();
            for (int i = size; i <= size * 2; ++i) {
                stock.push_back(&pool.emplace_back());
            }
            it = stock.begin() + size;
        }
    };
} // namespace suisen


#line 7 "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"

namespace suisen {
    template <typename T>
    struct PersistentFenwickTree {
        struct Node;

        using value_type = T;

        using node_type = Node;
        using node_pointer_type = node_type*;

        struct Node {
            static inline ObjectPool<node_type> _pool;

            node_pointer_type _ch[2]{ nullptr, nullptr };
            value_type _dat;

            Node() : _dat{} {}

            static node_pointer_type clone(node_pointer_type node) {
                return &(*_pool.alloc() = *node);
            }

            static node_pointer_type build(const std::vector<value_type> &dat, int p) {
                const int n = dat.size();
                std::vector<node_pointer_type> nodes(n + 1);
                auto rec = [&](auto rec, int p, int id) -> node_pointer_type {
                    if (p == 0) return nullptr;
                    const int np = p >> 1;
                    node_pointer_type res = _pool.alloc();
                    res->_ch[0] = rec(rec, np, id - np);
                    if (id + 1 <= n) res->_ch[1] = rec(rec, np, id + np);
                    if (id <= n) nodes[id] = res;
                    return res;
                };
                node_pointer_type res = rec(rec, p, p);
                for (int i = 1; i <= n; ++i) {
                    int par = i + (i & -i);
                    if (par <= n) nodes[par]->_dat += nodes[i]->_dat;
                }
                return res;
            }

            static value_type sum(node_pointer_type node, int p, int l, int r) {
                return sum(node, p, r) - sum(node, p, l);
            }

            static node_pointer_type add(node_pointer_type node, int p, int i, const value_type& val) {
                ++i;
                node_pointer_type res = clone(node);
                for (node_pointer_type cur = res;; p >>= 1) {
                    if (i & p) {
                        if (i ^= p) {
                            cur = cur->_ch[1] = clone(cur->_ch[1]);
                        } else {
                            cur->_dat += val;
                            return res;
                        }
                    } else {
                        cur->_dat += val;
                        cur = cur->_ch[0] = clone(cur->_ch[0]);
                    }
                }
            }
        private:
            static value_type sum(node_pointer_type node, int p, int r) {
                value_type res{};
                for (; r; p >>= 1) {
                    if (r & p) {
                        r ^= p;
                        res += node->_dat;
                        node = node->_ch[1];
                    } else {
                        node = node->_ch[0];
                    }
                }
                return res;
            }
        };

        PersistentFenwickTree() : _p(0), _root(nullptr) {}
        explicit PersistentFenwickTree(int n) : PersistentFenwickTree(std::vector<value_type>(n, T{})) {}
        PersistentFenwickTree(const std::vector<value_type>& dat) : _p(floor_pow2(dat.size())), _root(node_type::build(dat, _p)) {}

        static void init_pool(int size) {
            node_type::_pool = ObjectPool<node_type>(size);
        }
        static void clear_pool() {
            node_type::_pool.clear();
        }

        value_type sum(int l, int r) {
            return node_type::sum(_root, _p, l, r);
        }
        PersistentFenwickTree add(int i, const value_type &val) {
            return PersistentFenwickTree(_p, node_type::add(_root, _p, i, val));
        }

    private:
        int _p;
        node_pointer_type _root;
        PersistentFenwickTree(int p, node_pointer_type root) : _p(p), _root(root) {}

        static constexpr int floor_pow2(int n) {
            int x = 31 - __builtin_clz(n);
            return x < 0 ? 0 : 1 << x;
        }
    };
}
Back to top page