什么是线段树?

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

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

线段树模版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

建树

节点声明(区间: l , r)(状态值(最值): dat):

struct data{
int l,r,dat;
}t[4*N];

建树:

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

}

未完待续

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