segtree.cpp

// This is set up for range minimum queries, but can be easily adapted for computing other quantities.
// To enable lazy propagation and range updates, uncomment the following line.
// #define LAZY
struct Segtree {
	int n;
	vector<int> data;
#ifdef LAZY
#define NOLAZY 2e9
#define GET(node) (lazy[node] == NOLAZY ? data[node] : lazy[node])
	vector<int> lazy;
#else
#define GET(node) data[node]
#endif
	void build_rec(int node, int* begin, int* end) {
		if (end == begin+1) {
			if (data.size() <= node) data.resize(node+1);
			data[node] = *begin;
		} else {
			int* mid = begin + (end-begin+1)/2;
			build_rec(2*node+1, begin, mid);
			build_rec(2*node+2, mid, end);
			data[node] = min(data[2*node+1], data[2*node+2]);
		}
	}
#ifndef LAZY
	void update_rec(int node, int begin, int end, int pos, int val) {
		if (end == begin+1) {
			data[node] = val;
		} else {
			int mid = begin + (end-begin+1)/2;
			if (pos < mid) {
				update_rec(2*node+1, begin, mid, pos, val);
			} else {
				update_rec(2*node+2, mid, end, pos, val);
			}
			data[node] = min(data[2*node+1], data[2*node+2]);
		}
	}
#else
	void update_range_rec(int node, int tbegin, int tend, int abegin, int aend, int val) {
		if (tbegin >= abegin && tend <= aend) {
			lazy[node] = val;
		} else {
			int mid = tbegin + (tend - tbegin + 1)/2;
			if (lazy[node] != NOLAZY) {
				lazy[2*node+1] = lazy[2*node+2] = lazy[node]; lazy[node] = NOLAZY;
			}
			if (mid > abegin && tbegin < aend)
				update_range_rec(2*node+1, tbegin, mid, abegin, aend, val);
			if (tend > abegin && mid < aend)
				update_range_rec(2*node+2, mid, tend, abegin, aend, val);
			data[node] = min(GET(2*node+1), GET(2*node+2));
		}
	}
#endif
	int query_rec(int node, int tbegin, int tend, int abegin, int aend) {
		if (tbegin >= abegin && tend <= aend) {
			return GET(node);
		} else {
#ifdef LAZY
			if (lazy[node] != NOLAZY) {
				data[node] = lazy[2*node+1] = lazy[2*node+2] = lazy[node]; lazy[node] = NOLAZY;
			}
#endif
			int mid = tbegin + (tend - tbegin + 1)/2;
			int res = INT_MAX;
			if (mid > abegin && tbegin < aend) 
				res = min(res, query_rec(2*node+1, tbegin, mid, abegin, aend));
			if (tend > abegin && mid < aend)
				res = min(res, query_rec(2*node+2, mid, tend, abegin, aend));
			return res;
		}
	}

	// Create a segtree which stores the range [begin, end) in its bottommost level.
	Segtree(int* begin, int* end): n(end - begin) {
		build_rec(0, begin, end);
#ifdef LAZY
		lazy.assign(data.size(), NOLAZY);
#endif
	}

#ifndef LAZY
	// Call this to update a value (indices are 0-based). If lazy propagation is enabled, use update_range(pos, pos+1, val) instaed.
	void update(int pos, int val) {
		update_rec(0, 0, n, pos, val);
	}
#else 
	// Call this to update range [begin, end), if lazy propagation is enabled. Indices are 0-based.
	void update_range(int begin, int end, int val) {
		update_range_rec(0, 0, n, begin, end, val);
	}
#endif
	// Returns minimum in range [begin, end). Indices are 0-based.
	int query(int begin, int end) {
		return query_rec(0, 0, n, begin, end);
	}
};