segtree.sublime-snippet

<snippet>
	<content><![CDATA[
const int MAX = 1e5 + 5;
const int LIM = 3e5 + 5;        //equals 2 * 2^ceil(log2(n))
int a[MAX];
int seg[LIM];

int combine(int &a, int &b) {
	return a + b;
}

void build(int t, int i, int j) {
	if (i == j) {
		seg[t] = a[i];
		return ;
	}
	int mid = (i + j) / 2;
	build(t*2, i, mid);
	build(t*2 + 1, mid + 1, j);
	seg[t] = combine(seg[2*t], seg[2*t+1]);
}

void update(int t, int i, int j, int x, int y) {
	if (i > x || j < x) {
		return ;
	}
	if (i == j) {
		//base case : leaf node information to be stored here
		seg[t] = y;
		return ;
	}
	int mid = (i + j) / 2;
	update(t*2, i, mid, x, y);
	update(t*2 + 1, mid + 1, j, x, y);
	seg[t] = combine(seg[2*t], seg[2*t+1]);
}

int query(int t, int i, int j, int l, int r) {
	if (l <=i && j <= r) {
		return seg[t];
	}
	int mid = (i + j) / 2;
	if (l <= mid) {
		if (r <= mid) {
			return query(t*2, i, mid, l, r);
		}
		else {
			int a = query(t*2, i, mid, l, r);
			int b = query(t*2 + 1,  mid + 1, j, l, r);
			return combine(a, b);
		}
	}
	else {
		return query(t*2 + 1,  mid + 1, j, l, r);
	}
}
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>segtree</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<scope>source.cpp, source.c++, source.c</scope>
	<!-- Optional: Description to show in the menu -->
	<description>Segment Tree</description>
</snippet>