seg_tree.hpp

#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;
		}
	};
}

test.cpp

#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);
}