guhl37

星河滚烫，你是人间理想

线段树从入门到弃疗

发布于 2020-07-07 | 分类于 笔记 | 10分钟 | 2192字数

[TOC]

Ps: 本文代码部分未经压力测试，不保证完全正确，如有错误请联系博主

Introduction

许多算法的本质是统计\large\text{许多算法的本质是统计}

  • 什么是线段树

线段树(Segment Tree)是一种基于分治思想的二叉树结构，用于区间上信息的统计，相较于基于二进制进行区间划分的树状数组而言，线段树是一种更加通用的数据结构，而且代码量仅比树状数组大亿点点

本文将会侧重于进阶内容，如果你没学过或者不熟悉线段树请看这里线段树学习笔记

  • 什么时候用到线段树

统计量可以合并，修改量可以合并，通过修改量可直接修改统计量

满足区间加法即可使用线段树维护信息

普通线段树

储存

这里使用结构体储存线段树，我不太喜欢开一堆数组
在理想的情况下，NN个叶子节点的满二叉树有N+N2+N4+⋯+2+1=2N−1N+\frac{N}{2}+\frac{N}{4}+\cdots+2+1=2N-1个节点，当时由于使用这种存储方法会在最后一层产生空余，所以数组要开到4N4N

struct SegmentTree
{
    int l,r;//该节点的区间
    int dat;//维护的信息
}t[N*4];//4N!

建树

在区间[1,n][1,n]上建立线段树，注意最后要从下往上传递信息

void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].dat=a[l];return ;}
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].dat=max(t[p<<1].dat,t[p<<1|1].dat);
}

单点修改

相当于修改区间[x,x][x,x]，只需要递归找到代表这个区间的叶子节点，然后修改，再从下往上更新一下即可

复杂度为O(log⁡n)O(\log n)

int change(int p,int x,int y)
{
    if(t[p].l==t[p].r){t[p].dat=y;return;}
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) change(p<<1,x,y);
    else change(p<<1|1,x,y);
    t[p].dat=max(t[p<<1].dat,t[p<<1|1].dat);
}

区间查询

查询是会把询问的区间[l,r][l,r]在线段树上分成log⁡n\log n个节点，所以复杂度为O(log⁡n)O(\log n)

int ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].dat;//完全包含
    int mid=(t[p].l+t[p].r)>>1;
    int ret=-(1<<30);
    if(l<=mid) val=max(val,ask(p<<1,l,r));
    else val=max(val,ask(p<<1|1,l,r));
    return ret;
}

例题

CH4301 Can you answer on these queries III

CH4301

维护一个序列，支持单点修改和查询区间[x,y][x,y]中的最大连续子段和

问题在于如何维护最大连续字段和，或者说怎么存下最大连续子段和能让它满足区间加法，这也是用线段树维护某个东西时要考虑的核心问题

考虑最大连续字段和的形成方式，可能是整个区间[l,r][l,r]的和，可能是紧靠ll这边的一段连续和，可能是紧靠rr这边的一段连续和

所以我们可以在线段树中额外维护区间和sumsum，左端最大连续子段lmaxlmax和和右端连续子段和rmaxrmax，以及最大连续字段和datdat

只需要在从下往上更新的地方注意这几个量的关系，进行维护即可求解，转移的时候有点像区间dpdp

特别注意：此时如果x>yx>y，请交换x,yx,y

代码见CH4301 Can you answer on these queries III

CH4302 Interval GCD

CH4302

维护序列，实现区间加和询问区间的最大公约数

最大公约数怎么维护啊,qwqqwq

老祖宗写的《九章算术》告诉我们gcd⁡(x,y)=gcd⁡(x,y−x)\gcd(x,y)=\gcd(x,y-x)，实际上这个性质对三个数仍然成立，即gcd⁡(x,y,z)=gcd⁡(x,y−x,z−y)\gcd(x,y,z)=\gcd(x,y-x,z-y)，更实际上，该性质对任意多整数的都成立。（我不会整理，不过书上提示用数学归纳法）

因此我们只需要维护差分数组的区间最大公约数即可，这样就满足区间加法了。

至于区间加就按照差分数组的经典办法处理即可

延迟标记

又称懒标记，是一种"延迟“的思想。

懒标记提供了线段树中从上往下传递信息的方式，实现起来也很简单只需要再额外记录一个标记，在向下的操作中不断检查是否存在标记，并且不断下放即可

代码和普通线段树的相差不大，就是多了一个下放

void pushdown()
{
	if(t[p].lazy)
    {
        t[p<<1].dat+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1);
        t[p<<1|1].dat+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1);
        t[p<<1].lazy+=t[p].lazy;t[p<<1|1].lazy+=t[p].lazy;
        t[p].lazy=0;
	}
}

其他操作不再赘述

扫描线

用于求nn个矩形的面积并，矩形周长，多边形面积等问题。

扫描线-1

扫描线的思想如下

用一条竖直的直线（不一定，也可以别的方向）从左到右扫过整个坐标系，直线上被并集图形覆盖的长度只会在每个矩形的左右边界处发生改变，也就是将整个并集图形分割成2∗n2*n个段，每一段覆盖直线的长度是固定的，所以各段面积很容易求得，各段面积求和即为并集图形的面积

介于本文主要侧重于进阶内容，故不详细讲解扫描线了，仅大概说一下核心思路

注意事项

  • 用来维护高的线段树和一般的线段树有所不同，他的叶子节点是满足[l,r],l+1=r[l,r],l+1=r的
  • 如果坐标有小数(或值域过大)
  • 大概这些，想到再加

例题

Atlantis

Atlantis

nn个矩形放在一起，求它们的面积并

/*
@ author:pyyyyyy/guhl37
-----思路------

-----debug-------
太久没写其他头文件了，都忘了
memset必须用#include <cstring>
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define ls (rt << 1) 
#define rs (rt << 1 | 1)
using namespace std;
const int N = 2020;
int cover[N];
double len[N], yy[N];
struct SegmentTree{
	double x;//边x的坐标
	double upy, downy;//边上方的y坐标,下方的y坐标
	int inout;//标记是出边还是入边 
}line[N];
int cmp(SegmentTree &a, SegmentTree &b){
	return a.x < b.x;
}
void pushup(int rt, int l, int r)
{
	if(cover[rt]) len[rt] = yy[r] - yy[l];
	else if(l + 1 == r) len[rt] = 0;//到达叶节点
	else len[rt] = len[ls] + len[rs]; 
}
void update(int rt, int yl, int yr, int val, int l, int r)
{
//	if(yl > r || yr < l) return ;
	if(yl <= l && yr >= r)
	{
		cover[rt] += val;
		pushup(rt, l, r);
		return ;
	}
	if(l + 1 == r) return ;
	int mid = (l + r) >> 1;
	if(yl <= mid) update(ls, yl, yr, val, l, mid);
	if(yr > mid) update(rs, yl, yr, val, mid, r);//注意这里，不是mid+1，因为这里的线段树要进入[1,2][2,3]这样的区间
	pushup(rt, l, r); 
	
}
void add(int cnt, double x, double by, double ay, int val)
{
	line[cnt].downy = ay;
	line[cnt].upy = by;
	line[cnt].x = x;
	line[cnt].inout = val;
}
int n, T;
double  ax, ay, bx, by;//注意别用y1 
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(scanf("%d",&n),n)
	{
		memset(line, 0, sizeof(line));
		memset(yy, 0, sizeof(yy));
		int cnt=0;
		for(int i = 1; i <= n; ++i)
		{
			scanf("%lf %lf %lf %lf",&ax, &ay, &bx, &by);
			add(++cnt, ax, by, ay, 1); yy[cnt] = ay;
			add(++cnt, bx, by, ay, -1); yy[cnt] = by;
		}
		sort(yy + 1,yy + cnt + 1);
		sort(line + 1, line + cnt + 1, cmp);
		int Len = unique(yy + 1, yy + cnt + 1) - yy - 1;
		double ans = 0;
		for(int i = 1; i <= cnt; ++i)
		{
			ans += len[1] * (line[i].x - line[i - 1].x);
			int yl, yr, val;
			yl = lower_bound(yy + 1, yy + Len + 1, line[i].downy) - yy;
			yr = lower_bound(yy + 1, yy + Len + 1, line[i].upy) - yy;
			val = line[i].inout;
			update(1, yl, yr, val, 1, Len);
		}
		printf("Test case #%d\nTotal explored area: %.2f\n\n", ++T, ans);
	}
	return 0;
}

HDU1828 Picture

Picture

nn个矩形放在一起，求覆盖的周长并。

求周长的并，比求面积的并跟复杂一点

要解决两个部分：横线和竖线

先更到这里

# 笔记
杂题选刷 下一篇
0%
召唤看板娘