线段树

发表于 更新于 分类于 阅读次数： Changyan：

线段树

push up 由子节点算父节点的信息
push down操作 （懒标记/延迟标记）

将父节点的修改信息下传到子节点

1
2
3
4
5
6
7
8
9
10
11
//传入节点编号，用子节点信息来算父节点信息
push up（int u）
    
//将一段区间初始化为一颗线段树
build()
    
//修改操作,修改某一个点或者某一个区间（懒标记）
modify()
    
//查询某一段区间的信息
query()
定义：

线段树是一颗满二叉树；以一棵长度为10的序列为例:

对于图中的段从上到下，从左到右依次编号为1，2，3 …..

因此某一段 u 的左儿子是 u<<1 ，右儿子是 u<<1|1 。

线段树的结构
1
2
3
4
5
//一般使用结构体来存储线段树,空间大小开四倍
struct Node{
    int l,r;  //维护的区间
    int v;   //维护的信息...
} tree[N*4];
线段树的建树：
1
2
3
4
5
6
7
8
//build
void build(int u,int l,int r){ //构建节点u，其维护的是区间[l,r]
    tr[u]={l,r};
    if(l==r) return ; //已经是叶子节点
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    push_up(u);
}
push_up操作
1
2
3
4
//push_up操作,用子节点信息来更新父节点信息,以维护最大值为例
void push_up(int u){
    tree[u].v=max(tree[u<<1].v,tree[u<<1|1].v);
}
查询操作
1
2
3
4
5
6
7
8
9
10
//query操作，用来查询某一段区间内的信息,以最大值为例
int query(int u,int l,int r){  //从u节点开始查询[l,r]区间内的某一信息
    if(tree[u].l>=l&&tree[u].r<=r) return tree[u].v;  //说明这一段的信息已经被完全包含，因此不需要继续向下递归，直接返回即可
    int res=0;
    //否则需要判断该递归那一边
    int mid=tree[u].l+tree[u].r >> 1;
    if(l<=mid) res=max(res,query(u<<1,l,r));  //递归左边并更新信息
    if(mid<r) res=max(res,query(u<<1|1,l,r));  //递归右边并更新信息,切记是mid<r，无等号
    return res;
}
修改操作
1
2
3
4
5
6
7
8
9
10
//modify操作，用来修改某一叶子节点并更新其所有父节点
void modify(int u,int x,int v){   //从u节点开始递归查找，将编号为x的节点的值修改为v
    if(tree[u].l==x&&tree[u].r==x) tree[u].v=v;
    else{
        int mid=tree[u].l+tree[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        push_up(u);
    }
}

懒标记（延迟标记）push_down操作

  • 为了支持区间的修改操作，线段树添加了延迟标记。
  • 延迟标记，即在修改的时候对修改的区间上进行标记，
  • 在查找或者下一次修改的时候，用父区间的懒标记更新当前区间的懒标记，并更新当前区间的信息。换而言之，在修改指令的时候遇到完整区间直接更新并回溯，但在回溯前增加标记。当后续指令需要递归此节点时，根据标记跟新此节点的两个儿子节点，并将标记传给儿子节点。
  • 懒标记的意义表面此节点曾经被修改过，但是其儿子尚未被更新

添加懒标记后的更新的线段树函数

push_down通过父节点来更新子节点
1
2
3
4
5
6
7
8
//push_down操作既可以先更新再标记，也可以先标记再更新。此处我更习惯于先更新，后标记,此处以维护区间和的信息为例
void push_down(int u){
    Node &root=tree[u], &left=tree[u<<1], &right=tree[u<<1|1];
    left.add+=root.add;  //更新左儿子的懒标记
    left.sum=(left.r-left.l+1)*root.add;  //更新左儿子的信息
    right.add+=root.add;  //更新右儿子的懒标记
    right.sum=(right.r-right.l+1)*root.add;  //更新右儿子的信息
}
query查询函数
1
2
3
4
5
6
7
8
9
10
11
12
13
long long query(int u,int l,int r){ 
	if(tree[u].l>=l&&tree[u].r<=r) return tree[u].sum;
    push_down(u);  //先更新一下子节点
    int mid=tree[u].l+tree[u].r>>1; 
    if(r<=mid) return query(u<<1,l,r);  //只需要搜索左儿子
    else if(l>mid) return query(u<<1|1,l,r); //只需要搜索右儿子
    else{
        long long suml,sumr;
        if(l<=mid) suml+=query(u<<1,l,r);
        if(r>mid) sum2+=query(u<<1|1,l,r);
        return suml+sumr;
    }
}
modify修改函数
1
2
3
4
5
6
7
8
9
10
11
12
void modify(int u,int l,int r,int d){
    if(tree[u].l>=l&&tree[u].r<=r) {
        tree[u].sum+=(tree[u].r-tree[u].l+1)*d; //先标记
        tree[u].add+=d;     //然后标记
        return ;
    }
    push_down(u);  //先更新子节点
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,d); //如果有在mid左边的部分，修改左儿子
    if(r>mid) modify(u<<1|1,l,r,d); //有右儿子的部分，修改右儿子
    push_up(u);  //更新父节点
}
当有多个需要维护的懒标记时，即有多个懒标记的时候：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void cal(Node &root,int add,int mul){
    root.sum=root.sum*mul+add*(root.r-root,l+1);
    root.mul=root.mul*mul;
    root.add=root.add*mul+add;
}
//用子节点来更新父节点
void push_up(int u){
	tree[u].sum=tree[u<<1].sum+tr[u<<1|1].sum;
    tree[u].add=0,tree[u].mul=1;
}
//用父节点来更新子节点
void push_down(int u){
    cal(tree[u<<1],tree[u].add,tree[u].mul);
    cal(tree[u<<1|1],tree[u].add,tree[u].mul);
    //恢复
    root.add=0,root.mul=1;
}

扫描线

在有重复覆盖的长方形面积题型中，使用线段树维护区间扫描线：

长方形左侧为+1线，右侧为-1线，使用线段树可动态维护，修改一段区间或者获取一段区间内区间的长度

值得注意的是边界问题

1
2
3
4
5
Node{
    int l,r;  //维护的是最左侧区间的左端点和最右侧区间的右端点
    int cnt;  //维护的是各区间扫描线的覆盖次数
    double len; //维护的是扫描线长度
}