Naive Segment Tree

segtree.cc

#include <iostream>
#include <vector>

template<typename T>
struct Node
{
	T value;
	unsigned inf, sup;
	Node<T> *left, *right;
	
	Node(T value, unsigned inf, unsigned sup, Node<T> *left=nullptr, Node<T> *right=nullptr)
		: value(value), inf(inf), sup(sup), left(left), right(right)
	{
	}
	
	Node(unsigned inf, unsigned sup, Node<T> *left, Node<T> *right=nullptr)
		: inf(inf), sup(sup), left(left), right(right)
	{
		update();
	}
	
	void update()
	{
		if(left != nullptr && right != nullptr)
		{
			value = std::min(left->value, right->value);
		}
		else if(left != nullptr)
		{
			value = left->value;
		}
		else if(right != nullptr)
		{
			value = right->value;
		}
	}
};

template<typename T>
class SegmentTree
{
private:
	Node<T> *root;

	void debug(const std::vector<Node<T>*> &pool)
	{
		for(unsigned i=0; i<pool.size(); ++i)
		{
			std::cerr << "[" << pool[i]->inf << ", " << pool[i]->sup << "]: " << pool[i]->value << std::endl;
		}
		std::cerr << std::endl;
	}
	
	void modify_aux(Node<T> *node, unsigned index, T value)
	{
		if(node->inf == node->sup && node->inf == index)
		{
			node->value = value;
			return;
		}
		
		if(node->left->inf <= index && index <= node->left->sup)
		{
			modify_aux(node->left,  index, value);
			node->update();
		}
		else
		{
			modify_aux(node->right, index, value);
			node->update();
		}
	}
	
	void debug(Node<T> *node, int tab=0)
	{
		for(int t=0; t<tab; ++t) std::cerr << "\t";
		
		if(node->left == nullptr && node->right == nullptr)
		{
			std::cerr << node->inf << ": " << node->value << std::endl;
		}
		else if(node->left == nullptr)
		{
			std::cerr << "[" << node->inf << ", " << node->sup << "] : " << node->value << std::endl;
			debug(node->right, tab+1);
		}
		else if(node->right == nullptr)
		{
			std::cerr << "[" << node->inf << ", " << node->sup << "] : " << node->value << std::endl;
			debug(node->left, tab+1);
		}
		else
		{
			std::cerr << "[" << node->inf << ", " << node->sup << "] : " << node->value << std::endl;
			debug(node->left, tab+1);
			debug(node->right, tab+1);
		}
	}
	
	T query_aux(Node<T> *node, unsigned left, unsigned right)
	{
		if(node->inf == left && node->sup == right)
		{
			return node->value;
		}
		else if(node->left != nullptr && node->left->inf <= left && right <= node->left->sup)
		{
			return query_aux(node->left,  left, right);
		}
		else if(node->right != nullptr && node->right->inf <= left && right <= node->right->sup)
		{
			return query_aux(node->right, left, right);
		}
		else if(
			node->left != nullptr && node->right != nullptr && 
			node->left->inf  <= left  && left  <= node->left->sup &&
			node->right->inf <= right && right <= node->right->sup
		)
		{
			return std::min(
				query_aux(node->left,  left, node->left->sup),
				query_aux(node->right, node->right->inf, right)
			);
		}
	}
	
public:
	SegmentTree()
	{
		root = nullptr;
	}
	
	void build(auto begin, auto end)
	{
		std::vector<Node<T>*> pool[2];
		for(auto itr = begin; itr != end; ++itr)
		{
			unsigned index = std::distance(begin, itr);
			pool[0].push_back(new Node<T>(*itr, index, index));
		}
		debug(pool[0]);

		unsigned count = 0;
		while(pool[count & 1].size() > 2)
		{
			pool[(count + 1) & 1].clear();
			for(unsigned i=0; i<(pool[count & 1].size() >> 1); ++i)
			{
				pool[(count + 1) & 1].push_back(new Node<T>(
					pool[count & 1][i << 1]->inf,
					pool[count & 1][(i << 1) + 1]->sup,
					pool[count & 1][i << 1], 
					pool[count & 1][(i << 1) + 1]
				));
			}
			if(pool[count & 1].size() & 1 == 1)
			{
				pool[(count + 1) & 1].push_back(new Node<T>(
					pool[count & 1][pool[count & 1].size() - 1]->inf, 
					pool[count & 1][pool[count & 1].size() - 1]->sup,
					pool[count & 1][pool[count & 1].size() - 1], 
					nullptr
				));
			}
			debug(pool[(count + 1) & 1]);
			++count;
		}
		
		if(pool[count & 1].size() == 1)
		{
			root = new Node<T>(
				pool[count & 1][0]->inf, 
				pool[count & 1][0]->sup,
				pool[count & 1][0], 
				nullptr
			);
		}
		else
		{
			root = new Node<T>(
				pool[count & 1][0]->inf, 
				pool[count & 1][1]->sup,
				pool[count & 1][0], 
				pool[count & 1][1]
			);
		}
	}
	
	T query(unsigned left, unsigned right)
	{
		return query_aux(root, left, right);
	}
	
	void modify(unsigned index, T value)
	{
		modify_aux(root, index, value);
	}
	
	void tree() { debug(root); }
	
	T getValue() const { return root->value; }
};

int main()
{
	std::vector<int> v = {{ 32, 11, 15, 67, 8, 24, 19, 45, 27 }};
	SegmentTree<int> tree;
	tree.build(v.begin(), v.end());
	std::cerr << tree.getValue() << std::endl;
	
	tree.tree();	
	tree.modify(3, 1);
	tree.tree();
	
	std::cerr << tree.query(1, 2) << std::endl;
	std::cerr << tree.query(3, 6) << std::endl;
	std::cerr << tree.query(4, 7) << std::endl;
	std::cerr << tree.query(5, 8) << std::endl;
	
	return 0;
}