超级用心的线段树介绍

本文主要是介绍超级用心的线段树介绍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷同步。

前：笔者觉得线段树很重要，听说我基友___X3___要写一篇关于线段树的博客，我就也写了一篇介绍详细易懂的博客。持续更新。

-----------------------咕咕的分界线------------------------------------------------

更新日志：

update 11.21/2020 :写成。

-----------------------咕咕的分界线------------------------------------------------

Part 1

线段树是一种基于分治思想的二叉树结构，较通用，适于解决区间问题。

线段树的每个节点代表一个区间，根节点唯一，表示 $1 - n$ 。

每个叶节点表示一个长度为1的元区间 $[x, x]$ 。

对于每个节点（内部） $[l, r]$ ,它的左节点是 $[l, m i d]$ ，右子节点是 $[m i d + 1, r]$ 。

$m i d = (l + r) / 2 = (l + r) > > 1$

（ $m i d$ 向下取整）

-----------------------咕咕的分界线------------------------------------------------

性质：线段树除去最后一层，一定是一棵完全二叉树，所以，在理想情况下， $n$ 个节点的线段树有
$n + n / 2 + n / 4 + . . . + 2 + 1 = 2 n - 1$
个节点。

因此，数组长度要开到不小于4倍。

~~我暴力开过100倍，不会MLE…~~

-----------------------咕咕的分界线------------------------------------------------

图片链接：（图老是挂，于是决定使用链接。）

注意，线段树的编号与堆的编号类似，相当于 $d f s$ 序。

线段树图片

------------所以，第一部分圆满结束---------------------------------

Part 2,标记延迟

这就是大名鼎鼎~~臭名远扬~~的 $l a z y t a g$ 。

先说一下标记延迟的作用：将一次区间修改的时间复杂度从 $O (n)$ 优化到 $O (l o g n)$ 。

本文 $l o g$ 默认为2。

如果在修改指令中，要修改节点 $p$ 代表的区间 $[l, r]$ 。正常的修改方法就是访问以它为根节点的子树并修改。复杂度是 $O (n)$ ，其中 $n$ 为此子树节点数。

但是，我们没有用到这个区间作为候选答案。所以，更新 $p$ 的整棵子树是浪费时间的徒劳行为。

怎么解决呢？？？

加入 $l a z y t a g$ ，懒标记。

ps:关于标记，还有一种叫做“标记永久化”的技巧。就是不下传标记，而是累计递归时产生的标记影响。这种做法局限性大，仅在二维线段树和可持久化线段树中有所应用。所以不介绍了。

懒标记的具体实现就是在回溯时向节点 $p$ 增加一个标记，表示“该节点在过去被修改了，但是它的子节点尚未被更新”。

后续操作中，如果要从 $p$ 往下递归，我们就再检查一下 $p$ 是否有标记。有，就根据标记更新 $p$ 的两个儿子,并往下增加标记，然后消除 $p$ 的标记。

这种优化叫做延迟标记，是一个高效率的线段树应该具有的优化。

Part 3 ，Code

上代码。

线段树初始化：

struct segtree{int l,r,lazy,add;
}t[max_size<<1+max_size<<1];

有空更新一份用 $c l a s s$ 写的。

从子节点往父亲更新标记：

void pushup(int id)
{t[id].add=t[id<<1].add+t[id<<1|1].add;
}

下传标记：

void pushdown(int id,int l,int r){t[id<<1].lazy+=t[id].lazy;t[id<<1|1].lazy+=t[id].lazy;int mid=(l+r)>>1;t[id<<1].add+=t[id].lazy*(mid-l+1);t[id<<1|1].add+=t[id].lazy*(r-mid);t[id].lazy=0;	
}

线段树递归建立：

void build_segtree(int id,int l,int r){//节点id表示区间 [l,r]t[p].l=l,t[p].r=r;if(l==r){//叶节点t[p].add=a[l];return; }int mid=(l+r)>>1;build_segtree(id<<1,l,mid);build_segtree(id<<1|1,mid+1,r);//等同于build_segtree(id*2+1,mid+1,r); pushup(id);//标记延迟优化时间 
}

上传操作和下传操作是维护线段树的基本操作，基本上每一种操作都要用到。

还有，每个人的线段树写的都不一样，我的写法适中。所以，关于线段树，尽量不要背模板，要随机应变。

有一种比较经典的 $s p r e a d$ 函数，其实就是 $p u s h d o w n$ 函数。

单点修改和区间修改中很重要的一点：

判断是否向下递归，需判断覆盖性，如果当前区间 $[l, r]$ 被完全覆盖，就可以直接返回了。就是一种整块的处理，有没有分块的感觉？

单点修改，将区间 $[x, y]$ 的每一个值加上 $v$ ：

int add_(int id,int l,int r,int x,int y,int v){if(x<=l&&r<=y){t[id].lazy+=v;t[id].add+=v*(r-l+1);return;//叶节点修改 }pushdown(id,l,r);int mid=(l+r)>>1;if(x<=mid)add_(id<<1,l,mid,x,y);if(y>mid)add_(id<<1|1,mid+1,r,x,y);pushup(id);
}

区间修改,求出区间 $[x, y]$ 的每一个值的和：

int query(int id,int l,int r,int x,int y){if(x<=l&&r<=y){return t[id].add;}pushdown(id,l,r);int ans=0,mid=(l+r)>>1;if(x<=mid)ans+=query(id<<1,l,mid,x,y);if(y>mid)ans+=query(id<<1|1,mid+1,r,x,y);return ans;
}