[线段树] 线段树进阶问题

区间覆盖问题

• 问题：x轴被一些线段覆盖，每根线段的起点、终点均不同，考虑x轴被覆盖住的总长度
  
• 若仅仅用一般的线段树方法，对于每一根线段都需要深到其最深处的那个单个长度节点，以此做标记。
• 更好的方法是对线段树的每一个节点都添加一个cover标记，当cover=1时，证明此节点及其下属节点均被覆盖。所以下虑过程就可以停止了。
  
  插入线段[6, 10]，即覆盖了6、7-8、9-10。又因为前面有一些已经被覆盖的节点，所以可以在上层节点合并，即若下层两个节点均被标记cover，则上层节点标记cover。

区间操作问题

• 当我们在线段树中维护区间和，若每次都对区间内的每个叶子节点进行操作，复杂度达到了 O(L logL)
• Lazy标记
  
  • 当对[1, 4]区间做+5的操作时，需要对[1, 3]与[4, 4]进行操作。因为引入了Lazy标签，所以就不需要对每一个叶子节点操作了。例如，当到[1, 3]时，[1, 3]已经被完全包含在了[1, 4]之中，所以对[1, 3]的sum+=5*3，对其Lazy值+5
  • 但是，所谓Lazy标签也只是延迟了对子节点的操作，实际当查询的时候，需要对Lazy节点下放。看例子：
    
    在查询[3, 3]子区间的sum时，走到[1, 3]区间发现存在一个Lazy。与前面的Cover相似，将[1, 3]的Lazy分别下放到两个子节点上，并删除[1, 3]的Lazy
  • 什么时候更新子区间？当已经标记过的区间有一部分被更改，那么这个区间的整体值就不是那么多了，标记就会被下传一层。若查询子区间，也需要再传一层

// 此处为模板代码
void pushDown(int p, int m) {
	if (lazy[p]) {
		lazy[p<<1] += lazy[p];
		lazy[p<<1|1] += lazy[p];
		sum[p<<1] += (m-(m>>1))*lazy[p];
		sum[p<<1|1] += (m>>1)*lazy[p];
		lazy[p] = 0;
	}
}

void update(int L, int R, int c, int l, int r, int p) {
	// 当前区间L-R整体需要被更改
	if (L <= l && R >= r) {
		lazy[p] += c;
		sum[p] += (long long) c*(r-l+1);
		return;
	}
	// 当前区间不被更改或部分被更改
	pushDown(p, r-l+1);
	int mid = (l+r)>>1;
	if (L <= mid) update(L, R, c, l, mid, p<<1);
	if (R > mid) update(L, R, c, mid+1, r, p<<1|1);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}

long long query(int L, int R, int l, int r, int p) {
	if (L <= l && R >= r) return sum[p];
	pushDown(p, r-l+1);
	int mid = (l+r)<<1;
	long long ret = 0;
	if (L <= mid) ret += query(L, R, l, mid, p<<1);
	if (R > mid) ret += query(L, R, mid+1, r, p<<1|1);
	return ret;
}

离散化

• 将现有数据用更小的点进行映射操作

• 题目：POJ2528 在墙上贴海报，海报可以互相覆盖。问最后能看到几张海报？
  

  • 因为海报的数值都很大，所以考虑对其进行离散化操作。
  • 可以对贴海报的顺序进行反序：即先考虑后贴的海报，再考虑先贴的海报。（为什么？维护一个线段树，当后贴的某一张海报在update的时候，发现其之前的状态没有被完全覆盖，说明这张海报一定可以被看到 — 简化操作）
  • 如果区间被覆盖，标记Lazy为True

  int find(int p, int l, int r) {
  	if (tree[p].lazy) return false;	// 区间已经被覆盖
  	if (tree[p].l==l && tree[p].r==r) {
  		tree[p].lazy = true;
  		return true;
  	}
  	bool result;
  	int mid = (tree[p].l+tree[p].r)>>1;
  	if (r < mid) result = find(p<<1, l, r);
  	else if (l > mid) result = find(p<<1|1, l, r);
  	else {
  		bool r1 = find(p<<1, l, mid);
  		bool r2 = find(p<<1|1, mid+1, r);
  		result = r1 || r2;
  	}
  	if (tree[p<<1].lazy && tree[p<<1|1].lazy) tree[p].lazy = true;
  	return result;
  }
  

• 关于离散化的过程，这里还没有说的很清楚，会贴上一个题作为例子

• 部分内容来自于B站NPUACM的视频整理