线段树(学习笔记)

线段树

线段树是一种基于分治思想的二叉树结构,比树状数组更加通用,下文总结会比较这两种数据结构;

线段树的基本用途是对序列进行维护,支持查询与修改指令;

线段树的每个节点都代表一个区间;

线段树具有唯一的根节点,代表的是整个区间,即[1,n];

线段树的每个叶节点都代表一个长度为1的区间,即[x,x];

对于每个内部节点[l,r],它的左子节点是[l,mid],右子节点是[mid+1,r],其中mid=(l+r)/2(向下取整);(子节点与父节点的性质近似于二叉堆的结构);

保存的数组长度要不小于4*n;

1 建树:线段树的二叉树结构可以很方便地从下往上传递信息;

下面以区间最大值为例:

struct TREE{
	int l,r;
    int dat;
}t[n*4];
//一般会用结构体存储线段树

void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;//节点p代表区间[l,r]
    if(l==r){t[p].dat=a[l];return;}//叶节点
    int mid=(l+r)/2;
    build(p*2,l,mid);//左子节点
    build(p*2+1,mid+1,r);//右子节点
    t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
    //从下往上传递信息
}

build(1,1,n);//调用入口

2 单点修改:线段树中,根节点(编号为1的节点)是执行各种指令的入口;上述建树过程中的调用入口的第一个1就是这个道理;

我们还是以区间最大值问题为例

void change(int p,int x,int v){
	if(t[p].l==t[p].r){t[p].dat=v;return;}
    //找到叶节点
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid) change(p*2,x,v);
    else change(p*2+1,x,v);
    //判断x属于哪边区间
    t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

change(1,x,v);

3 区间查询

以查询区间最大值为例:

若[l,r]完全覆盖了当前节点代表的区间,则立即回溯,并且该节点的dat值为候选答案

若左子节点与[l,r]有重叠部分,则递归访问左子节点;

若右子节点与[l,r]有重叠部分,则递归访问右子节点;

(这里自己稍微理解一下就懂了,或者自己画个图)

假设我们查询区间[2,7]的最大值,现在有一个节点的代表区间为[3,5],那么属于完全覆盖的情况,return,并且该节点的dat值为候选答案;

现在还有[2,3]和[5,7]这两个区间没有处理,我们继续寻找节点,如果有一个节点与该区间有交集,即有重叠的区间,我们就继续向下访问该节点,直至找到一个节点完全被[2,3]或[5,7]覆盖,那么跟上面一样处理即可;(记住我们是从上往下访问线段树,所以区间范围从上往下是越来越小的)

int ask(int p,int l,int r){
	if(l<=t[p].l&&r>=t[p].r)return t[p].dat;
    int mid=(t[p].l+t[p].r)/2;
    int val=-(1<<30);
    if(l<=mid) val=max(val,ask(p*2,l,r));
    if(r>mid) val=max(val,ask(p*2+1,l,r));
    return val;
}

ask(1,l,r);

延迟标记:标识该节点曾经被修改,但其子节点尚未被修改(即一个节点被打上延迟标记的同时,它自身保存的信息应该已经被修改完毕)

通俗地讲,我们在进行区间增加操作时,如果去更改区间中的每个数(即遍历到每个叶节点),时间复杂度会增加到O(N);

试想一下,有可能我们修改了该区间,但所有的查询中与该区间没有关系(即该区间没有对我们的答案产生贡献),相当于我们做了一次无用的操作;

于是就可以用到延迟标记,我们在执行修改指令时,给节点p一个标记,标识该节点曾经被修改,但其子节点尚未被修改,如果在后续的查询指令中,我们需要知道p节点的子节点的信息,如果p节点有标记,那么更新p的两个子节点,同时给p的两个子节点打上延迟标记,然后清除p的标记;

以区间增加问题为例:

void spread(int p){
    if(t[p].add){//如果节点P有标记
 t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
    //更新左子节点信息
t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
    t[p*2].add+=t[p].add;//给左子节点打延迟标记
    t[p*2+1].add+=t[p].add;
    t[p].add=0;//清除p的标记
    }
}

void change(int p,int x,int y,int v){
    if(x<=t[p].l&&y>=t[p].r){//完全覆盖
    	t[p].sum+=v*(t[p].r-t[p].l+1);
        //更新节点信息
    	t[p].add+=v;//给节点打上延迟标记
    	return;
    }
    spread(p);    //下传延迟标记
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid) change(p*2,x,y,v);
    if(y>mid) change(p*2+1,x,y,v);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

long long ask(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r) 
    	return t[p].sum;
    spread(p);//下传延迟标记
    int mid=(t[p].l+t[p].r)/2;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);
    return ans;
}

最后比较一下树状数组和线段树:

树状数组可以实现单点修改和区间求和(如果将序列进行差分,那么还可以实现区间价值和单点询问);

线段树能实现树状数组的所有操作,除此之外,还可以通过标记下传或标记永久化进行区间修改和区间询问;

但树状数组的常数比线段树小,实现也较为简单(线段树真的是随随便便100行,看来我还是太蒻了)

总之,能用树状数组就用树状数组吧,毕竟一般都只能用线段树;