Skip to content

Instantly share code, notes, and snippets.

@plasma-effect

plasma-effect/seg_tree.hpp

Last active May 14, 2019 01:53
Download ZIP

Revisions

  1. plasma-effect revised this gist May 14, 2019. 1 changed file with 6 additions and 26 deletions.
    32 changes: 6 additions & 26 deletions seg_tree.hpp
    View file
    Original file line number Diff line number Diff line change
    @@ -37,43 +37,23 @@ namespace lib
    }
    };

    template<class T>constexpr auto get_unit(std::plus<T>)
    template<class T, class U>auto get_unit(std::plus<U>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::plus<>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::multiplies<T>)
    {
    return T(1);
    }
    template<class T>constexpr auto get_unit(std::multiplies<>)
    template<class T, class U>auto get_unit(std::multiplies<U>)
    {
    return T(1);
    }
    template<class T>constexpr auto get_unit(std::bit_xor<T>)
    template<class T, class U>auto get_unit(std::bit_xor<U>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::bit_xor<>)
    {
    return T();
    }
    template<class T>constexpr auto get_unit(lib::min<T>)
    template<class T, class U>auto get_unit(lib::min<U>)
    {
    return std::numeric_limits<T>::max();
    }
    template<class T>constexpr auto get_unit(lib::min<>)
    {
    return std::numeric_limits<T>::max();
    }
    template<class T>constexpr auto get_unit(lib::max<T>)
    {
    return std::numeric_limits<T>::min();
    }
    template<class T>constexpr auto get_unit(lib::max<>)
    template<class T, class U>auto get_unit(lib::max<U>)
    {
    return std::numeric_limits<T>::min();
    }
    @@ -116,7 +96,7 @@ namespace lib
    }
    build();
    }

    void update(std::size_t i, T const& v)
    {
    i += sz;
  2. plasma-effect revised this gist May 14, 2019. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions seg_tree.hpp
    View file
    Original file line number Diff line number Diff line change
    @@ -17,9 +17,9 @@ namespace lib
    };
    template<>struct min<void>
    {
    template<class T>constexpr auto operator()(T&& lhs, T&& rhs)const
    template<class T>constexpr auto operator()(T const& lhs, T const& rhs)const
    {
    return std::min(std::forward<T>(lhs), std::forward<T>(rhs));
    return std::min(lhs, rhs);
    }
    };
    template<class T = void>struct max
    @@ -31,9 +31,9 @@ namespace lib
    };
    template<>struct max<void>
    {
    template<class T>constexpr auto operator()(T&& lhs, T&& rhs)const
    template<class T>constexpr auto operator()(T const& lhs, T const& rhs)const
    {
    return std::max(std::forward<T>(lhs), std::forward<T>(rhs));
    return std::max(lhs, rhs);
    }
    };

  3. plasma-effect created this gist May 14, 2019.
    158 changes: 158 additions & 0 deletions seg_tree.hpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,158 @@
    #pragma once
    #include<type_traits>
    #include<functional>
    #include<numeric>
    #include<algorithm>
    #include<boost/range/irange.hpp>
    #include<boost/range/adaptor/reversed.hpp>

    namespace lib
    {
    template<class T = void>struct min
    {
    constexpr T operator()(T const& lhs, T const& rhs)const
    {
    return std::min(lhs, rhs);
    }
    };
    template<>struct min<void>
    {
    template<class T>constexpr auto operator()(T&& lhs, T&& rhs)const
    {
    return std::min(std::forward<T>(lhs), std::forward<T>(rhs));
    }
    };
    template<class T = void>struct max
    {
    constexpr T operator()(T const& lhs, T const& rhs)const
    {
    return std::max(lhs, rhs);
    }
    };
    template<>struct max<void>
    {
    template<class T>constexpr auto operator()(T&& lhs, T&& rhs)const
    {
    return std::max(std::forward<T>(lhs), std::forward<T>(rhs));
    }
    };

    template<class T>constexpr auto get_unit(std::plus<T>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::plus<>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::multiplies<T>)
    {
    return T(1);
    }
    template<class T>constexpr auto get_unit(std::multiplies<>)
    {
    return T(1);
    }
    template<class T>constexpr auto get_unit(std::bit_xor<T>)
    {
    return T(0);
    }
    template<class T>constexpr auto get_unit(std::bit_xor<>)
    {
    return T();
    }
    template<class T>constexpr auto get_unit(lib::min<T>)
    {
    return std::numeric_limits<T>::max();
    }
    template<class T>constexpr auto get_unit(lib::min<>)
    {
    return std::numeric_limits<T>::max();
    }
    template<class T>constexpr auto get_unit(lib::max<T>)
    {
    return std::numeric_limits<T>::min();
    }
    template<class T>constexpr auto get_unit(lib::max<>)
    {
    return std::numeric_limits<T>::min();
    }

    constexpr std::size_t get_size(std::size_t s)
    {
    std::size_t i = 1;
    while (i < s)
    {
    i <<= 1;
    }
    return (i >> 1) == s ? s : i;
    }

    template<class T, class Op>class seg_tree
    {
    std::vector<T> vec;
    Op op;
    std::size_t sz;
    const T unit;

    void build()
    {
    for (auto s : boost::irange<std::size_t>(1, sz) | boost::adaptors::reversed)
    {
    vec[s] = op(vec[2 * s], vec[2 * s + 1]);
    }
    }
    public:
    seg_tree(std::size_t s) :vec(), op(Op()), sz(get_size(s)), unit(get_unit<T>(Op()))
    {
    vec.assign(2 * sz, unit);
    }
    template<class Range>seg_tree(Range const& rng) : seg_tree(rng.size())
    {
    auto i = sz;
    for (auto const& v : rng)
    {
    vec[i++] = v;
    }
    build();
    }

    void update(std::size_t i, T const& v)
    {
    i += sz;
    vec[i] = v;
    while (i >>= 1)
    {
    vec[i] = op(vec[2 * i], vec[2 * i + 1]);
    }
    }

    T get(std::size_t a, std::size_t b)const
    {
    auto L = unit;
    auto R = unit;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1)
    {
    if (a & 1)
    {
    L = op(L, vec[a++]);
    }
    if (b & 1)
    {
    R = op(vec[--b], R);
    }
    }
    return op(L, R);
    }

    T const& operator[](std::size_t i)
    {
    return vec[sz + i];
    }

    std::size_t size()const
    {
    return sz;
    }
    };
    }
    50 changes: 50 additions & 0 deletions test.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,50 @@
    #include<iostream>
    #include<vector>
    #include"segtree.hpp"

    template<class T, class Op>void write_tree(lib::seg_tree<T, Op>const& tree)
    {
    auto size = tree.size();
    for (std::size_t i : boost::irange<std::size_t>(0, size))
    {
    for (std::size_t j : boost::irange<std::size_t>(1, size + 1))
    {
    std::cout << tree.get(i, j) << " ";
    }
    std::cout << std::endl;
    }
    }

    int main()
    {
    std::vector<int> test = { 1,2,3,4,5,6,7,8 };

    lib::seg_tree<int, std::plus<>> tree1(test);
    write_tree(tree1);
    std::cout << std::endl;
    tree1.update(1, 4);
    tree1.update(3, 6);
    tree1.update(5, 8);
    tree1.update(7, 2);
    write_tree(tree1);
    std::cout << std::endl;

    lib::seg_tree<int, lib::max<int>> tree2(test.size());
    for (auto i : boost::irange<std::size_t>(0, test.size()))
    {
    tree2.update(i, test[i]);
    }
    write_tree(tree2);
    std::cout << std::endl;
    tree2.update(1, 4);
    tree2.update(1, 6);
    tree2.update(1, 8);
    tree2.update(1, 2);
    write_tree(tree2);
    std::cout << std::endl;

    std::vector<int> test2 = { 1,2,4,8,16,32,64,128 };
    lib::seg_tree<int, std::bit_xor<>> tree3(test2);
    std::cout << std::hex;
    write_tree(tree3);
    }