线段树笔记

线段树是一种高级的数据结构，可以用来维护区间信息。基本原理是（以下面长度为5的线段树为例）：

每个点维护一个值，例如区间和。

定义左儿子和右儿子。

inline int ls(int n){return n<<1;}
inline int rs(int n){return n<<1|1;}

接下来需要一些 基本操作：

首先，建树。

void build(int i,int l,int r){
    if(l==r){//叶子节点
        scanf("%lld",&sg[i]);//点i所维护的区间和就是该点的值
        return ;
    }
    int mid=(l+r)/2;
    build(ls(i),l,mid);//左子树
    build(rs(i),mid+1,r);//右子树
    sg[i]=sg[ls(i)]+sg[rs(i)];//更新维护的值
}

接着，单点修改：

void update(int p,int l,int r,int x,int v){
    if(l==r)sg[p]=v;//如果就是这个点，赋值
    else{	
        int mid=(l+r)/2;   
	if(x<=mid)update(ls(p),l,mid,x,v);//如果目标点在右子树，向右递归
	else update(rs(p),mid+1,r,x,v);//否则向左递归
	sg[p]=sg[ls(p)]+sg[rs(p)];//
    }
}

最后，区间查询：

long long sum(int p,int l,int r,int x,int y){
    if(x<=l&&y>=r)return sg[p];
    int ans=0,mid=l+r>>1;
    if(x<=mid)ans+=sum(ls(p),l,mid,x,y);
    if(y>mid)ans+=sum(rs(p),mid+1,r,x,y);
    return ans;
}