segtree.snippets

snippet segment_tree
template<typename st_node>
struct segment_tree {
	int size = 0;
	vector<st_node> arr;

	segment_tree(vector<st_node> v) {
		size = v.size();
		arr.resize(2*size);
		for (int i = size; i < 2*size; ++i)
			arr[i] = v[i-size];
		for (int i = size-1; i >= 1; --i)
			arr[i] = arr[2*i].comb(arr[2*i+1]);
	}

	segment_tree(int t, st_node x) : segment_tree(vector<st_node>(t, x)) { }

	void upd(int pos, st_node val) {
		pos += size; arr[pos] = val;
		while (pos > 1) {
			pos /= 2;
			arr[pos] = arr[2*pos].comb(arr[2*pos+1]);
		}
	}

	void refresh(int pos, st_node refr) {
		upd(pos, arr[pos+size].comb(refr));
	}

	void add(int pos, ll delta) {
		upd(pos, arr[pos+size].value+delta);
	}

	st_node get(int lo, int ri) {
		lo += size;
		ri += size+1;
		st_node res; 
		while (lo < ri) {
			if (lo & 1)
				res = res.comb(arr[lo++]);
			if (ri & 1)
				res = res.comb(arr[--ri]);
			lo /= 2; ri /= 2;	
		}
		return res;
	}
};

$0
endsnippet

snippet st_node
struct ${1:st_node} {
	${2:datatype} value;
	$1() : value(${3:be_careful}) {}
	$1($2 x) : value(x) {} 
	operator $2() { return value; }
	min32 comb(const min32 &oth) {
		return ${4:OP}; 
	}
};
$0
endsnippet

snippet min32
struct min32 {
	int value;
	min32() : value(1e9) {}
	min32(int x) : value(x) {} 
	operator int() { return value; }
	min32 comb(const min32 &oth) {
		return min(value, oth.value); 
	}
};
$0
endsnippet

snippet max32
struct max32 {
	int value;
	max32() : value(-1e9) {}
	max32(int x) : value(x) {} 
	operator int() { return value; }
	max32 comb(const max32 &oth) {
		return max(value, oth.value); 
	}
};
$0
endsnippet

snippet sum32
struct sum32 {
	int value;
	sum32() : value(0) {}
	sum32(int x) : value(x) {} 
	operator int() { return value; }
	sum32 comb(const sum32 &oth) {
		return value + oth.value; 
	}
};
$0
endsnippet


snippet min64
struct min64 {
	ll value;
	min64() : value(2e18) {}
	min64(ll x) : value(x) {} 
	operator ll() { return value; }
	min64 comb(const min64 &oth) {
		return min(value, oth.value); 
	}
};
$0
endsnippet

snippet max64
struct max64 {
	ll value;
	max64() : value(-2e18) {}
	max64(ll x) : value(x) {} 
	operator ll() { return value; }
	max64 comb(const max64 &oth) {
		return max(value, oth.value); 
	}
};
$0
endsnippet

snippet sum64
struct sum64 {
	ll value;
	sum64() : value(0) {}
	sum64(ll x) : value(x) {} 
	operator ll() { return value; }
	sum64 comb(const sum64 &oth) {
		return value + oth.value; 
	}
};
$0
endsnippet