gistfile1.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <utility>
#include <fstream>
#include <map>
#include <cmath>
#include <functional>
#include <exception>
#include <stdexcept>
#include <sstream>

namespace data_structure {

template<class T, class C = std::less<T> >
class segment_tree {
  static const int ROOT = 1;

private:
	std::vector<int> tree;
	std::vector<T> data;
	C comparator;

public:
	/**
	 * Required tree size is:
	 *		2*2^(floor(log2(N)) + 1) ~ 2*2*2^(log2(N)) = 4
	 */
	segment_tree(const std::vector<T> &data) :
			tree(data.size() * 4 + 1, 0), data(data) {
		build(ROOT, 0, data.size() - 1);
	}

	segment_tree(const T data[], int size) :
			tree(size * 4, 0) {
		this->data.assign(data, data + size);
		build(ROOT, 0, size - 1);
	}

	T query(int low, int high) const {
		int idx = query(ROOT, 0, data.size() - 1, low, high);
		if (idx == -1) {
			throw std::range_error(get_message_error(low, high));
		}
		return data[idx];
	}

	const T operator [](int i) const {
		return data[i];
	}

	unsigned size() const {
		return data.size();
	}

private:
	const char* get_message_error(int i, int j) const {
		std::ostringstream ostr;
		ostr << "Out of range query(" << i << ", " << j << ")";
		return ostr.str().c_str();
	}

	/**
	 *  Query from a range (i, j)
	 */
	int query(int root, int low, int high, int i, int j) const {
		if (i > high || j < low) {
			return -1;
		}
		if (i <= low && high <= j) {
			return tree[root];
		}
		int middle = (low + high) / 2;
		int l_idx = query(2 * root, low, middle, i, j);
		int h_idx = query(2 * root + 1, middle + 1, high, i, j);
		if (l_idx == -1) {
			return h_idx;
		}
		if (h_idx == -1) {
			return l_idx;
		}
		return comparator(data[l_idx], data[h_idx]) ? l_idx : h_idx;
	}

	/**
	 * Build segment tree starting from root == 1
	 */
	void build(int root, int low, int high) {
		if (low == high) {
			tree[root] = low;
		} else {
			// left child  : 2*root
			int lc = (root << 1);
			// right child : 2*root + 1
			int rc = (lc | 1);
			// middle = (low + high) / 2;
			int middle = low + ((high - low) >> 1);
			build(lc, low, middle);
			build(rc, middle + 1, high);
			int l_idx = tree[lc];
			int h_idx = tree[rc];
			if (comparator(data[l_idx], data[h_idx])) {
				tree[root] = l_idx;
			} else {
				tree[root] = h_idx;
			}
		}
	}
};

void test() {
	int a[7] = { 8, 7, 3, 9, 5, 1, 10 };
	std::vector<int> v(a, a + 7);

	segment_tree<int> lst(v);
	std::cout << lst.query(1, 3) << '\n';
	std::cout << lst.query(4, 6) << '\n';

	segment_tree<int, std::greater<int> > gst(a, 7);
	std::cout << gst.query(1, 3) << '\n';
	std::cout << gst.query(4, 6) << '\n';

	for (int i = 0; i < 7; ++i) {
		std::cout << gst[i] << ',';
	}
}