Skip to content

Instantly share code, notes, and snippets.

@plasma-effect
Last active May 14, 2019
Embed
What would you like to do?
#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 const& lhs, T const& rhs)const
{
return std::min(lhs, 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 const& lhs, T const& rhs)const
{
return std::max(lhs, rhs);
}
};
template<class T, class U>auto get_unit(std::plus<U>)
{
return T(0);
}
template<class T, class U>auto get_unit(std::multiplies<U>)
{
return T(1);
}
template<class T, class U>auto get_unit(std::bit_xor<U>)
{
return T(0);
}
template<class T, class U>auto get_unit(lib::min<U>)
{
return std::numeric_limits<T>::max();
}
template<class T, class U>auto get_unit(lib::max<U>)
{
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;
}
};
}
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment