\(NOIP\)阶段只要不涉及区间翻转、区间插入的序列问题都可以用线段树实现。

每一个节点维护一个区间的信息。

线段树有分治的感觉。

线段树可以处理很多符合结合律的操作。

时间复杂度，建树为\(O(n)\)，区间查询和区间修改为\(O(log\ n)\)。

空间要开原序列长度的四倍。

查询的话就是序列分割，由于分割次数近似\(log\) \(n\)，故总复杂度为\(O(n\ log\ n)\)

\(code:\)

void pushup(int cur)
{
    val[cur]=val[ls[cur]]+val[rs[cur]];
}
void pushdown(int cur,int l,int r)
{
    if(!lazy[cur]) return;
    lazy[ls[cur]]+=lazy[cur];
    lazy[rs[cur]]+=lazy[cur];
    int mid=(l+r)>>1;
    val[ls[cur]]+=lazy[cur]*(mid-l+1);
    val[rs[cur]]+=lazy[cur]*(r-mid);
    lazy[cur]=0;
}
void build(int L,int R,int &cur)
{
    cur=++tree_cnt;
    if(L==R)
    {
        val[cur]=a[L];
        return;
    }
    int mid=(L+R)>>1;
    build(L,mid,ls[cur]);
    build(mid+1,R,rs[cur]);
    pushup(cur);
}
void modify(int L,int R,int l,int r,ll add,int cur)
{
    if(L<=l&&R>=r)
    {
        val[cur]+=add*(r-l+1);
        lazy[cur]+=add;
        return;
    }
    pushdown(cur,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) modify(L,R,l,mid,add,ls[cur]);
    if(R>mid) modify(L,R,mid+1,r,add,rs[cur]);
    pushup(cur);
}
ll query(int L,int R,int l,int r,int cur)
{
    if(L<=l&&R>=r) return val[cur];
    pushdown(cur,l,r);
    ll sum=0;
    int mid=(l+r)>>1;
    if(L<=mid) sum+=query(L,R,l,mid,ls[cur]);
    if(R>mid) sum+=query(L,R,mid+1,r,rs[cur]);
    return sum;
}

......

build(1,n,root);//建树
modify(x,y,1,n,z,root);//区间修改，x到y的区间加上z
query(x,y,1,n,root)//区间查询，x到y的和

动态开点

\(code:\)

void pushup(int cur)
{
    val[cur]=val[ls[cur]]+val[rs[cur]];
}
void pushdown(int cur,int l,int r)
{
    if(!lazy[cur]) return;
    int mid=(l+r)>>1;
    if(!ls[cur]) ls[cur]=++tree_cnt;
    lazy[ls[cur]]+=lazy[cur];
    val[ls[cur]]+=lazy[cur]*(mid-l+1);
    if(!rs[cur]) rs[cur]=++tree_cnt;
    lazy[rs[cur]]+=lazy[cur];
    val[rs[cur]]+=lazy[cur]*(r-mid);
    lazy[cur]=0;
}
void modify(int L,int R,int l,int r,ll add,int &cur)
{
    if(!cur) cur=++tree_cnt;
    if(L<=l&&R>=r)
    {
        val[cur]+=add*(r-l+1);
        lazy[cur]+=add;
        return;
    }
    pushdown(cur,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) modify(L,R,l,mid,add,ls[cur]);
    if(R>mid) modify(L,R,mid+1,r,add,rs[cur]);
    pushup(cur);
}
ll query(int L,int R,int l,int r,int cur)
{
    if(L<=l&&R>=r) return val[cur];
    pushdown(cur,l,r);
    ll sum=0;
    int mid=(l+r)>>1;
    if(L<=mid) sum+=query(L,R,l,mid,ls[cur]);
    if(R>mid) sum+=query(L,R,mid+1,r,rs[cur]);
    return sum;
}

线段树合并

将\(x\)和\(y\)合并为\(x\)

通常用来合并权值线段树（一个节点权值为其值域区间元素个数）

更新信息时要特判叶子节点的情况，防止信息覆盖

\(code:\)

int merge(int x,int y)
{
    if(!x||!y) return x+y;
    ls[x]=merge(ls[x],ls[y]);
    rs[x]=merge(rs[x],rs[y]);
    pushup(x);
    return x;
}

线段树优化建图

\(code:\)

void build_in(int L,int R,int &cur)
{
    cur=++tree_cnt;
    if(L==R)
    {
        in_num[L]=cur;
        return;
    }
    int mid=(L+R)>>1;
    build_in(L,mid,ls[cur]);
    build_in(mid+1,R,rs[cur]);
    add(ls[cur],cur,0),add(rs[cur],cur,0);
}
void build_out(int L,int R,int &cur)
{
    cur=++tree_cnt;
    if(L==R)
    {
        out_num[L]=cur;
        return;
    }
    int mid=(L+R)>>1;
    build_out(L,mid,ls[cur]);
    build_out(mid+1,R,rs[cur]);
    add(cur,ls[cur],0),add(cur,rs[cur],0);
}
void modify_in(int L,int R,int l,int r,int pos,int val,int &cur)
{
    if(L<=l&&R>=r)
    {
        add(cur,pos,val);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) modify_in(L,R,l,mid,pos,val,ls[cur]);
    if(R>mid) modify_in(L,R,mid+1,r,pos,val,rs[cur]);
}
void modify_out(int L,int R,int l,int r,int pos,int val,int &cur)
{
    if(L<=l&&R>=r)
    {
        add(pos,cur,val);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) modify_out(L,R,l,mid,pos,val,ls[cur]);
    if(R>mid) modify_out(L,R,mid+1,r,pos,val,rs[cur]);
}