线段树

线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。

1. 线段树的每个节点都代表一个区间
2. 线段树具有唯一的根节点，代表的区间是整个统计范围，如[1,n]
3. 线段树的每个叶节点都代表一个长度为1的元区间
4. 对于每个内部节点[l,r]，它的左子节点是[l,mid]，右子节点是[mid+1,r]，其中mid=(l+r)>>1

线段树的建树

void build(int rt,int l,int r){
	tree[rt].l=l;
	tree[rt].r=r;
	if(l==r){
		tree[rt].sum=tree[rt].max=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	tree[rt].sum=tree[lson].sum+tree[rson].sum;
	tree[rt].max=max(tree[lson].max,tree[rson].max);
}
    build(1,1,n);//调用入口

线段树的单点修改

void update(int rt,int pos,int val){
	if(tree[rt].l==tree[rt].r){
		tree[rt].sum+=val;
		tree[rt].max=val;
		return;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(pos<=mid) update(lson,pos,val);
	else update(rson,pos,val);
	tree[rt].sum=tree[lson].sum+tree[rson].sum;
	tree[rt].max=max(tree[lson].max,tree[rson].max);
}
update(1,pos,val);//调用入口

线段树的区间查询

int query(int rt,int l,int r){
	if(tree[rt].l > r or tree[rt].r < l) return 0;
	if(l<=tree[rt].l&&tree[rt].r<=r) return tree[rt].sum;
	int mid=(tree[rt].l+tree[rt].r)>>1;
	int val=0;
	if(l<=mid) val+=Query(lson,l,r);
	if(r>mid) val+=Query(rson,l,r);
	return val; 
}
cout<<query(1,l,r)<<endl;//调用入口