线段树

标签：Lazy 标记线段 Tag 区间矩形

3. 区间操作与 Lazy-Tag

本节介绍线段树的核心操作 Lazy-Tag，并给出区间修改 \(+\) 区间查询的模板。

在线段树上，如果直接进行区间修改，时间复杂度为 \(\mathcal{O}(N \log N)\)。而 Lazy-Tag 可以将其降为 \(\mathcal{O}(\log N)\)。

Lazy-Tag 方法

用 \(lz_p\) 统一记录区间 \(p\) 的修改。也就是说，如果整个区间 \(p\) 都需要修改，那么只修改一下 \(lz_p\) 即可。直到要访问这个区间的子区间时，再将这个标记随递归向下传。这样时间复杂度就变为 \(\mathcal{O}(\log N)\) 了。

向下传递函数 push_down()

当要访问一个区间的子区间时，应将这个区间的 Lazy-Tag 传递给下面的两个子区间，并删除这个区间的 Lazy-Tag。这样可以保持最后这个区间的值不变。

如果一个线段树的 Lazy-Tag 为加法标记，那么传递的函数如下。

void tag(int p,int l,int r,int k){
	t[p]+=(r-l+1)*k;
	/*打上标记：总值的变化*/
	lz[p]+=k;
	/*打上标记：Lazy-Tag的变化*/
}
void push_down(int p,int l,int r){
	int mid=(l+r)>>1;
	tag(ls(p),l,mid,lz[p]);
	tag(rs(p),mid+1,r,lz[p]);
	/*将Lazy-Tag传递个下面的两个子区间*/
	lz[p]=0;
	/*清除标记*/
}

由于是区间加，当没有标记的时候相当于加零，不会影响结果，所以不需要判断是否有标记。但如果是区间赋值就需要判断了。

模板代码

例1 洛谷-P3372

本题为线段树的模板题。大部分函数中都有 \(p,l,r\) 三个参数，其中 \(p\) 表示这个区间在 \(t\) 数组的下标（区间和），\(l,r\) 表示这个区间在 \(a\) 数组的下标。

代码

例2 洛谷-P3373

再使用一个乘法标记。初始时都为 \(1\)。

打加法标记

更新区间总和，更新加法标记。

打乘法标记

更新区间总和，更新乘法标记，将加法标记也乘上更新的数。

向下传递标记

儿子结点的总和先乘上父亲的乘法标记，再加上父亲的加法标记 \(\times\) 儿子结点的区间长度。

儿子结点的加法标记先乘上父亲的乘法标记，再加上父亲的加法标记。

儿子结点的乘法标记直接乘上父亲的乘法标记。

还要注意取模，实现比较麻烦。可以参考代码理解。

代码

7. 扫描线

扫描线算法是线段树的经典应用，它能解决矩阵面积并、矩阵周长并、多边形面积等几何问题。

1. 矩阵面积并

例1 HDU-1542 翻译

下图是两个矩形 \(S,W\)。可以将其转化为三个矩形 \(A,B,C\)，总面积不变。

矩阵面积 \(=\) 长 \(\times\) 宽。它们的宽很容易计算，但它们的长就比较麻烦了。

对于一个矩形，用入边表示它下面的边，出边表示它上面的边。这样从下到上扫描时，如果遇到入边，就说明进入了一个矩形；如果遇到出边，就说明离开了一个矩形。在上图（c）中，矩形 \(S\) 的入边是边 \(1\)，出边是边 \(3\)。

用 \(P_1,P_2,P_3\) 分别表示从左到右的 \(3\) 条线段的长度。所以 \(A\) 的宽 \(=P_1+P_2\)，\(B\) 的宽 \(=P_1+P_2+P_3\)，\(C\) 的宽 \(=P_2+P_3\)。求它们的宽，实际上就是判断这些线段要不要计算进去。如计算 \(C\) 是 \(P_2,P_3\) 需要计算进去。

定义标志 \(T_1,T_2,T_3\) 分别判断 \(P_1,P_2,P_3\) 是否要计算进去。在遇到入边时，\(T\) 加 \(1\)；在遇到出边时，\(T\) 减 \(1\)。可以发现，当 \(T>0\) 是需要计算进去。得到 \(T\) 值，就可以计算矩形 \(A,B,C\) 的宽了。

整个算法就使用扫描线从下到上扫过所有矩形，每次扫描都计算其中一层的面积。这就是扫描线算法。

以上模型，如何用线段树实现？可以让线段树的一个结点表示区间范围，如上图用结点 \(1,2,3\) 分别表示 \(P_1,P_2,P_3\)。将这些点看为叶子节点，从下向上扫描，如果是入边就加入线段，如果是出边就删除线段。

用线段树实现扫描线需要离散化。用结点 \(1,2,3\) 分别表示 \(P_1,P_2,P_3\) 即可。

时间复杂度为 \(\mathcal{O}(M \log N)\)。

读入所有矩形，记录入边和出边。
对所有边按 \(y\) 坐标排序，确定扫描顺序。
对 \(x\) 坐标做离散化。
从下向上扫描线段，用扫描到的线段更新线段树，每个结点的值是扫描线确定的新矩形。
对所有矩形求和。

代码

2. 矩阵周长并

例2 HDU-1828 翻译

周长问题和面积问题的思路差不多，但是复杂一点。下面给出两种方法。

1. 做两次扫描

总周长 \(=\) 总横线长 \(+\) 总竖线长。

以横线为例。将所有横线按 \(y\) 坐标升序排序，并分为入边和出边，分别用 \(1,-1\) 表示。

从下到上扫描，每次扫描就记录这部分的横线值。应计入的长度就等于现在总区间被覆盖的长度与上一次总区间被覆盖的长度之差的绝对值。这个不难理解。在新计入线段后，会有两种情况：

这条线段在总区间的内部

比如上图中最上方大矩形中的小矩形。在更新长度后，总长度不会变。而实际周长确实没有包含这条边。

这条线段一部分在总区间以外

比如上图中最左侧矩形的下面那条边。扫过这条线段后，区间总长度会加上它的左边部分，也就是说，现在的总长度与上次的总长度差了左边部分的长度。而实际周长确实计算了这部分的长度。

因此这个方法是正确的。同理可以计算竖线。

2. 做一次扫描

其实做一次就够了。在计算横线的同时可以将竖线也计算出来。

用 \(num\) 表示应计入总长度的竖边的数量，\(sum\) 表示计算的总周长。

每次扫到入边时，如果没有与它 \(y\) 坐标相同且已经扫过的入边，那么就会新加入两条线段，\(num \leftarrow num+2\)。这两条线段的长度即为这条横边与下一条横边的距离。设这个距离为 \(d\)，则 \(sum \leftarrow sum+d \times num\)

每次扫到出边时，如果没有与它 \(y\) 坐标相同且已经扫过的出边，那么就会减少两条线段，\(num \leftarrow num-2\)。

这样就能计算出总周长了。

代码

标签：Lazy,标记,线段,Tag,区间,矩形
From： https://www.cnblogs.com/lrxmg139/p/18012103