세그먼트 트리 코드

아래 코드에서 적절히 트리의 식만 변형해주면 구간 최대,최소,합,곱 세그트리를 만들어줄 수 있다.

세그트리는 복붙보단 매번 직접 짜는걸 추천한다.  

[ Code ] 

const int MAX = 100001;
struct segment_tree {
	int tree[4 * MAX];
	void upd(int node, int s, int e, int idx, int v) {
		if (idx<s || idx>e) return;
		if (s == e) {
			tree[node] = v;
			return;
		}
		int m = (s + e) / 2;
		upd(2 * node, s, m, idx, v);
		upd(2 * node + 1, m + 1, e, idx, v);
		tree[node] = tree[2 * node] + tree[2 * node + 1];
	}
	int query(int node, int s, int e, int qs, int qe) {
		if (s > qe || e < qs) return 0;
		if (qs <= s && e <= qe) return tree[node];
		int m = (s + e) / 2;
		int L = query(2 * node, s, m, qs, qe);
		int R = query(2 * node + 1, m + 1, e, qs, qe);
		return R + L;
	}
}seg;