线段树?

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

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为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;
}
}

推荐题

来做题吧!

载入天数...载入时分秒...