线段树?

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

查询 修改
朴素算法 O(n) O(1)
前缀和 O(1) O(n)
树状数组 O(log2 n) O(log2 n)
ST表 O(1) O(log2 n)
线段树 O(1) O(log2 n)
单调队列 O(1) 或许不能修改

线段树模版1

[区间最值，仅满足单点修改]

满足以下特性：

  1. 树中每一个节点，代表一个区间
  2. 根节点代表一个完整的期间[1,n]
  3. 每个叶子节点代表长度为1的区间[x,x]，即区间的一个元素
  4. 对于非叶子节点的每一个节点[l,r]，它的左儿子是[l,mid]，右儿子是[mid+1,r]。其中mid=(l+r)/2
  5. 一个完整二叉树中，根节点p的左儿子编号为p*2，右儿子编号为p*2+1。

Code< / >

  • 节点声明(区间: l , r)(状态值(最值): dat)：
struct data{
    int l,r,dat;
}t[4*N];
  • 建树(区间: l , r)(状态值(最值)dat)：
void build(int p,int l,int r) //p为当前的节点编号,l r 是当前要赋给t[p]的l r
{
    t[p].l=l,t[p].r=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); //最值，可换min
}
  • 询问某区间[l,r]的最值：

1.该节点全覆盖时不再往下递归，但需返回该节点的值

2.该节点取中点mid后,观察是那一边（中点左右）完全没有覆盖则不再往下递归;否则都需要往下递归（含半边全覆盖，因为下一层会直接返回值）

3.该节点需返回两边递归后处理的结果（当然，如果只有一边递归，就直接返回这一边的值）

int ask(int p,int l,int r)
{
    if(l<=t[p].l && t[p].r<=r) return t[p].dat;
		int mid=(t[p].l+t[p].r)/2;
  	int val=-999999999; //最值
    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;
}
  • 指定位置x ,修改值为v （递归过程同上）：
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);
  	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

线段树模版2

[满足区间修改] P3372 【模板】线段树 1

带延迟标记功能的线段树

核心代码

  • spread(int p)为延迟标记下移一层

注意：当该层打上标记后，表示该层内容已经修改，本层以下等待机会再修改。机会来之下一次修改或查询时经过此节点往下递归时。

void spread(int p)
{
    if(t[p].add>0){
    		t[2*p].dat+=t[p].add*(t[2*p].r-t[2*p].l+1);
				t[2*p+1].dat+=t[p].add*(t[2*p+1].r-t[2*p+1].l+1);		
				t[2*p].add+=t[p].add;
				t[2*p+1].add+=t[p].add;	
				t[p].add=0;
  	}	
}

推荐题

来做题吧！


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议


 上一页

栈