Дерево отрезков

gistfile1.cpp

#include <iostream>
#include <vector>
#include <stdexcept>
#include <iomanip>
#include <sstream>

template <class T>
class SumPolicy
{
public:
	T neutral() const
	{
		return T();
	}
	T operator()(T a, T b) const
	{
		return a + b;
	}
};


template <class T>
class MaxPolicy
{
public:
	MaxPolicy(T infinite):
		inf(infinite)
	{}

	T neutral() const
	{
		return inf;
	}
	T operator()(T a, T b) const
	{
		return std::max(a, b);
	}
private:
	T inf;
};


template <class T, template <typename = T> class Policy = SumPolicy >
class SegmentTree
{
public:
	template <class ForwardIterator>
	SegmentTree(ForwardIterator first, ForwardIterator last, const Policy<T>&);
	SegmentTree(const std::vector<T>& values, const Policy<T>&);

	T get(size_t index) const;
	T get(std::pair<size_t, size_t> slice) const;
	void set(size_t index, const T& value);

	void push_back(const T& elem);
	void pop_back();

private:
	size_t size;
	size_t realCount;
	std::vector<T> tree;
	Policy<T> policy;

	static size_t degreeOf2(size_t n);
	size_t indexInTree(size_t index) const;
	void makeTree(const std::vector<T>& values);
	void update(size_t node, size_t leftLimit, size_t rightLimit, size_t modified, T newValue);
	T calcSegment(size_t node, size_t leftLimit, size_t rightLimit, size_t left, size_t right) const;
};

int main()
{
	std::vector<int> v1;
	
	for (int i = 0; i < 10; ++i)
		v1.push_back(rand() % 10);

	SegmentTree<int, SumPolicy> tree1(v1, SumPolicy<int>());

	std::string answer;
	std::cout << "Задать запрос?" << std::endl;
	std::getline(std::cin, answer, '\n');
	while (answer == "y")
	{
		for (size_t i = 0; i < v1.size(); ++ i)
			std::cout << std::setw(3) << i;
		std::cout << std::endl;

		for (size_t i = 0; i < v1.size(); ++ i)
			std::cout << std::setw(3) << v1[i];
		std::cout << std::endl;

		size_t a, b;
		
		std::string query;
		std::getline(std::cin, query, '\n');
		std::istringstream(query) >> a >> b;
		
		std::cout << tree1.get(std::make_pair(a, b)) << std::endl;

		std::cout << "Задать запрос?" << std::endl;

		std::getline(std::cin, answer, '\n');

		size_t index = rand() % v1.size();
		v1[index] = rand() % 10;
		tree1.set(index, v1[index]);
	}
	
	return 0;
}


template <class T, template <typename = T> class Policy>
template <class ForwardIterator>
SegmentTree<T, Policy>::SegmentTree(ForwardIterator first, ForwardIterator last, const Policy<T>& policyObj):
policy(policyObj)
{
	policy = policyObj;

	std::vector<T> values;	
	std::copy(first, last, values.end());	

	makeTree(values);
}

template <class T, template <typename = T> class Policy>
SegmentTree<T, Policy>::SegmentTree(const std::vector<T>& values, const Policy<T>& policyObj):
policy(policyObj)
{
	makeTree(values);
}

template <class T, template <typename = T> class Policy>
void SegmentTree<T, Policy>::makeTree(const std::vector<T>& values)
{
	size = values.size();
	realCount = degreeOf2(values.size());
	tree.resize(realCount * 2 - 1, policy.neutral());

	for (size_t i = 0; i < size; ++i)
		tree[realCount - 1 + i] = values[i];

	size_t start = realCount / 2;
	size_t end = realCount;
	
	while (start != 0)
	{
		for (size_t i = start; i < end; ++i)
			tree[i - 1] = policy(tree[i*2 - 1], tree[i*2]);
	
		start /= 2;
		end /= 2;
	}
}

template <class T, template <typename = T> class Policy >
size_t SegmentTree<T, Policy>::degreeOf2(size_t n)
{
	size_t result = 1;
	while (result < n)
		result <<= 1;

	return result;
}

template <class T, template <typename = T> class Policy >
size_t SegmentTree<T, Policy>::indexInTree(size_t index) const
{
	return realCount + index - 1;
}

template <class T, template <typename = T> class Policy >
T SegmentTree<T, Policy>::get(size_t index) const
{
	if (index >= size)
		throw std::range_error("Index out of range");
	return tree[indexInTree(index)];
}

template <class T, template <typename = T> class Policy >
void SegmentTree<T, Policy>::set(size_t index,const T& value)
{
	if (index >= size)
		throw std::range_error("Index out of range"); 
	update(0, 0, realCount - 1, index, value);
}

template <class T, template <typename = T> class Policy >
void SegmentTree<T, Policy>::update(size_t node, size_t leftLimit, size_t rightLimit, size_t modified, T newValue)
{
	if (leftLimit == rightLimit)
	{
		tree[indexInTree(modified)] = newValue;			
		return;
	}

	size_t middle = (rightLimit + leftLimit) / 2;
	if (modified < middle)
		update((node+1)*2 - 1, leftLimit, middle, modified, newValue);
	else
		update((node+1)*2, middle + 1, rightLimit, modified, newValue);

	tree[node] = policy(tree[(node+1)*2 - 1], tree[(node+1)*2]);
}

template <class T, template <typename = T> class Policy >
T SegmentTree<T, Policy>::get(std::pair<size_t, size_t> slice) const
{
	if (slice.first >= size || slice.second >= size || slice.first > slice.second)
		throw std::range_error("Index out of range");

	return calcSegment(0, 0, realCount - 1, slice.first, slice.second);
}

template <class T, template <typename = T> class Policy >
T SegmentTree<T, Policy>::calcSegment(size_t node, size_t leftLimit, size_t rightLimit, size_t left, size_t right) const
{
	if (left > right)
		return policy.neutral();
	if (left == leftLimit && right == rightLimit)
		return tree[node];
	size_t middle = (leftLimit + rightLimit) / 2;
	return policy(calcSegment ((node+1)*2 - 1, leftLimit, middle, left, std::min(right,middle)),
		      calcSegment ((node+1)*2, middle+1, rightLimit, std::max(left,middle + 1), right));
}

template <class T, template <typename = T> class Policy >
void SegmentTree<T, Policy>::push_back(const T& elem)
{
	if (size != realCount)
	{
		++size;
		set(size - 1, elem);
	}
	else
	{
		std::vector<T> values;
		for (size_t i = 0; i < size; ++i)
			values.push_back(tree[realCount / 2 - 1 + i]);
		
		values.push_back(elem);
		SegmentTree tmp(values, policy);
		*this = tmp;
	}
}

template <class T, template <typename = T> class Policy >
void SegmentTree<T, Policy>::pop_back()
{
	if (size - 1 != realCount / 4)
	{
		set(size - 1, policy.neutral());
		--size;
	}
	else
	{
		std::vector<T> values;
		for (size_t i = 0; i < size - 1; ++i)
			values.push_back(tree[realCount / 2 - 1 + i]);
		SegmentTree tmp(values, policy);
		*this = tmp;
	}
}