线段树ADT

//Node Type
struct Node{
	int left, right;
	int max, sum;
} tree[maxn];
/*
tree[k]'s left child is tree[2*k], 
right child is tree[2*k+1];
*/

步骤一：建树

//Step 1: bulid
void build(int l, int r, int k)
{
	tree[k].left = l; tree[k].right = r;
	if(l == r){
		tree[k].sum = tree[k].max = arr[l];
		return;
	}
	
	int mid = (l + r) / 2;
	build(l, mid, 2 * k);
	build(mid + 1, r, 2 * k + 1);
	
	tree[k].sum = tree[2*k].sum + tree[2*k+1].sum;
	tree[k].max = max(tree[2*k].max, tree[2*k+1].max);
}

步骤二：更新

//Step 2: update
void update(int pos, int val, int k)
{
	if(tree[k].left == tree[k].right){
		tree[k].max = (tree[k].sum += val); 
		return;
	}
	
	int mid = (tree[k].left + tree[k].right) / 2;
	if(pos <= mid) update(pos, val, 2 * k);
	else update(pos, val, 2 * k + 1);
	
	tree[k].sum = tree[2*k].sum + tree[2*k+1].sum;
	tree[k].max = max(tree[2*k].max, tree[2*k+1].max);
}

步骤三：查询

//Step 3: query
int query(int l, int r, int k)
{
	if(tree[k].left == tree[k].right)
		return tree[k].sum; //or tree[k].max;
	
	int mid = (tree[k].left + tree[k].right) / 2;
	if(r <= mid) return query(l, r, 2 * k);
	else if(l > mid) return query(l, r, 2 * k + 1);
	return query(l, mid, 2*k) + query(mid+1, r, 2*k+1);
}