概念

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为$O(logn)$。

操作

下面我们从一个经典的例子来了解线段树

    从数组arr[0...n-1]中查找某个数组某个区间内的最小值,
    其中数组大小固定,但是数组中的元素的值可以随时更新。

我们可以用线段树来解决这个问题:预处理耗时$O(n)$,查询、更新操作$O(logn)$,需要额外的空间$O(n)$。根据这个问题我们构造如下的二叉树

  • 叶子节点是原始组数arr中的元素
  • 非叶子节点代表它的所有子孙叶子节点所在区间的最小值
    例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树(背景为白色表示叶子节点,非叶子节点的值是其对应数组区间内的最小值,例如根节点表示数组区间arr[0…5]内的最小值是1):

由于线段树的父节点区间是平均分割到左右子树,因此线段树是完全二叉树,对于包含$n$个叶子节点的完全二叉树,它一定有$n-1$个非叶节点,总共$2n-1$个节点,因此存储线段是需要的空间复杂度是$O(n)$

创建线段树

子节点

根据线段树的性质(完全二叉树),只需知道父节点,就可以计算出子节点的序号

inline LL getLeftNum(LL p)
{
    return p<<1;
}
inline LL getRightNum(LL p)
{
    return p<<1|1;
}

树的存放和节点信息

首先,我们需要判断我们需要维护的对象,可以是一个,也可以是颜色状态

struct
{
    int val;//可以添加col,status,lztag
}Tree[N];

建树操作

我们使用递归操作来建树

  • 当左端点和右段点相同时,意味着此时的$p$节点是叶子节点
  • 二分当前区间,递归建树

注意,这里有两个尚未出现的东西,$pushup$函数和$lztag$标记

$pushup$函数用于从子节点向上依次更新父节点的值
而$lztag$是用于区间修改的懒标记

void buildTree(LL p,LL l,LL r)
{
    lztag[p]=0;
    if(l==r) {Tree[p]=a[l];return ;}
    LL mid=(l+r)>>1;
    buildTree(getLeftNum(p),l,mid);
    buildTree(getRightNum(p),mid+1,r);
    pushup(p);
}

pushup 操作

$pushup$起到更新的作用,对于不同的需求,有不同的$pushup$操作

对于求和,可以这么写

inline void pushup(LL p)
{
    Tree[p]=Tree[getLeftNum(p)]+Tree[getRightNum(p)]);
}

而对于求 最大值/最小值 ,则可以这么写

inline void put_up(LL p)
{
    Tree[p]=max(Tree[getLeftNum(p)],Tree[getRightNum(p)]);
    //Tree[p]=min(Tree[getLeftNum(p)],Tree[getRightNum(p)]);
}

更新操作

更新操作可以分为两种

  • 单点操作
  • 区间操作

单点操作(updataPot)

明确变量名:

  1. (l ~ r) —— 可支配区间
  2. (nedChangeL ~ nedChangeR) —— 需操作区间
  3. mid —— 可支配区间中点

注 :

  • 当$mid$不小于$nedChangeL$时 代表去 $l$ ~ $mid$ 更新是有意义的,所以,我们选择更新该区间
  • $mid$和$nedChangeR$同理
void updataPot(LL nedChangeL,LL nedChangeR,LL l,LL r,LL p,LL num)
{
    if(l==r) {Tree[p]=num;return ;}
    LL mid=(l+r)>>1;
    if(nedChangeL<=mid) updata(nedChangeL,nedChangeR,l,mid,getLeftNum(p),num);
    if(nedChangeR>mid) updata(nedChangeL,nedChangeR,mid+1,r,getRightNum(p),num);
    put_up(p);
}

区间操作(updataInterval)

#区间操作需要引入一个概念

$lazytag$ :
$lazytag$标注的是线段树中每个树的变化量,即 $\Delta$

$lazytag$ 操作时正如其名,只对目前状态打上标记,等到更新时,才向下传递
因此,引入另一个函数$pushdown$,用于更新其子节点的$lazytag$和本节点的数值

接下来给出$pushdown$的代码

inline void updataSum(LL p,LL l,LL r,LL num)
{
    lztag[p]=lztag[p]+num;
    Tree[p]+=num*(r-l+1);
}
inline void put_down(LL p,LL l,LL r)
{
    LL mid=(l+r)>>1;
    updataSum(getLeftNum(p),l,mid,lztag[p]);
    updataSum(getRightNum(p),mid+1,r,lztag[p]);
    lztag[p]=0;
}

有了$pushdown$算法,我们可以完成$updata$操作

void updataInterval(LL needChangeL,LL needChangeR,LL l,LL r,LL p,LL num)
{
    if(needChangeL<=l&&r<=needChangeR) {updataSum(p,l,r,num);return ;}
    put_down(p,l,r);
    LL mid=(l+r)>>1;
    if(needChangeL<=mid) updata(needChangeL,needChangeR,l,mid,getLeftNum(p),num);
    if(needChangeR>mid) updata(needChangeL,needChangeR,mid+1,r,getRightNum(p),num);
    put_up(p);
}

区间求值(query)

区间求值时,我们进行了询问,而因为$lazytag$的原因,在求值之前,需先进行$pushdown$操作

LL getSum(LL qx,LL qy,LL l,LL r,LL p)
{
    LL sum=0;
    if(qx<=l&&r<=qy)return Tree[p];
    LL mid=(l+r)>>1;
    put_down(p,l,r);
    if(qx<=mid)sum+=getSum(qx,qy,l,mid,getLeftNum(p));
    if(qy>mid) sum+=getSum(qx,qy,mid+1,r,getRightNum(p));
    return sum;
}

END


CODE_LIFE