「数据结构学习笔记」#1 线段树相关

线段树上二分

用形式化的语言讲，线段树上二分求解的是这一类问题。

给定 \(L\)，找到一个 \(R \in [L,n]\) 满足 \[ f \Big( op\big([L,R-1]\big) \Big) = 1 \] \[ f\Big( op\big(R\big) \Big)=0 \]

其中 \(f\) 为某种合法性函数，\(op\) 是将区间信息合并为 \(f\) 能处理的信息的过程。

int query(int L,int& S,int x,int l,int r);

其中 \(S\) 为当前已经合并的区间信息，\(x: [l,r]\) 为当前节点。

如何进行求解？既然要以 \(L\) 为左端点进行区间合并，那么无论何时我们都优先递归左儿子，对于一个 \([l,r]\)，若 \(r<L\)，就不再往下递归了。

此后便一定能找到 \(L \le l\)，且第一次找到时一定满足 \(L=l\)，于是就合并信息。如果此时 \(f(S)=1\)，那么往继续往右边找，结束递归。如果 \(f(S)=0\) 且 \(l=r\)，答案 \(R=l\)。

如果 \(l < L \operatorname{ and } L \le r\)，往下递归即可。

借用严格鸽的图，不难看出合并区间的过程是连续的。按顺序合并了 \(7,8,9,10,11\)，在 \(12\) 处找到了答案。

那这玩意复杂度是多少？

找 \(L\) 的过程相当于优先递归左端点的单点查找，但是如果和 \([L,n]\) 无交便不会递归下去，复杂度 \(O(\log_2 n)\)。
之后只有合并后 \(f\) 值为 \(0\) 才往下递归，否则就合并信息。临界点又是固定的，所以每递归一次区间长度就减半，所以复杂度还是 \(O(\log_2 n)\)。

因此总复杂度 \(O(\log_2n)\)。

下面给出模板。

int query(int L,node& S,int x=1,int l=1,int r=n) {
	if(r<L) return -1;
	if(L<=l) {
		if(f(op(S,x))) {
			S=op(S,x);
			return -1;
		}
		if(l==r) return l;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	int res=query(L,S,x<<1,l,mid);
	if(res==-1) return query(L,S,x<<1|1,mid+1,r);
	return res;
}

这种带着引用的写法存在一定局限性，但是某种程度上更加便于理解。

考虑这样一个模板题

维护一个 01 序列，求 \([L,n]\) 从左往右第 \(k\) 个 1 的位置。

转化为

给定 \(L\)，找到 \(R\) 满足 \([L,R-1]\) 中有不超过 \(k\) 个 \(1\)。

因此node& S就是当前还需要找到 \(S\) 个 \(k\)，op(S,x)就是 \(S\) 减去区间内 \(1\) 的个数，\(f\) 就是看是不是大于 \(0\)（还要给 \(R\) 留一个 1 的位置）。

这玩意的用法很灵活。

luogu4198 楼房重建

\(n\) 点 \(m\) 次操作，每次操作单点修改，操作完之后查询全局有多少 \(a_i\)，满足对于 \(j \in [1,i-1]\)，\(a_j < a_i\)。规模 \(10^5\)。

由于只查全局，所以考虑线段树直接维护。设 \(s\big(x:[l,r]\big)\) 为 \([l,r]\) 内满足条件的 \(a_i\) 的个数，\(t\big(x:[l,r]\big)\) 为 \([l,r]\) 内的最大值。

对于一个区间 \(x:[l,r]\)，首先它会直接继承 \(s(x)\)，然后加上 \([mid+1,r]\) 中的一个子序列，满足严格递增且第一个元素大于 \(t(x)\)。

看起来不好做，但是考虑那第一个大于 \(t(x)\) 的值，如果它在某个节点 \(y\) 的左儿子内，那么其右儿子内大于它的数量一定是 \(s(y)-s\big(lson(y)\big)\)。

这样线段树上二分，在 \([mid+1,r]\) 内查找第一个大于 \(t\big(lson(x)\big)\) 的数，顺便加上上面那个即可。

CF1440E Greedy Shopping

\(n\) 个点 \(m\) 次操作，一种操作是前缀取 \(\max\)，另一种操作是给定 \(L\) 和 \(k\)，从 \(L\) 到 \(n\)，如果到 \(i\) 时有 \(a_i \le k\)，那么就让让答案加 1，\(k-a_i\)，表示购买。\(\{a\}\) 单调不增，规模 \(2 \cdot 10^5\)。

容易看出来购买的一定是若干个连续段。

单独求一个连续段是容易的，在 \([L,n]\) 上查找第一个满足 \(Sum[L,i+1] > k\) 的 \(i\) 即可。多个的话，可以再二分第一个小于等于剩下的 \(k\) 的位置。

考虑一个性质，如果已经无法购买，说明剩下的 \(k\) 不会多于之前的一半了，否则由于序列单调，必然可以购买，所以最多二分 \(O(\log_2 \max\{Y\})\) 次。

然后记录区间最小值可以做到可行性剪枝。

考虑前缀取 \(\max\) 的操作，区间内是有不同的数的，比较好的解决方法是记录区间最大值，只在取 \(\max\) 的值不小于区间最大值时再打标记，pushup维护即可。

这玩意也能在权值线段树（主席树）上用。

动态开点

很多时候值域很大又不能离散化，为了降低空间复杂度，可以抛弃二叉树的结构，直接记录左右儿子，且一个节点被创建当且仅当被使用到。

如果是动态操作且值域较大，那么可以考虑动态开点。

那么如果一次操作复杂度是 \(O(\log_2 n)\) 的话，用到的节点数也是 \(O(\log_2n)\) 的，\(m\) 次操作时候节点数量为 \(O(m \log_2 n)\)。

写法倒是很简单，而且能直接套上普通线段树的pushup和pushdown。

void modify(int& x,int p,int l=1,int r=n) {
	if(x==0) x=++cnt;
	if(l==r) {
		ls[x]=rs[x]=0;
        // init a node.
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) modify(ls[x],p,l,mid);
	else modify(rs[x],p,mid+1,r);
	pushup(x);
}

下面是摘自OI-wiki的两段代码。

// root 表示整棵线段树的根结点；cnt 表示当前结点个数
int n, cnt, root;
int sum[n * 2], ls[n * 2], rs[n * 2];

// 用法：update(root, 1, n, x, f); 其中 x 为待修改节点的编号
void update(int& p, int s, int t, int x, int f) {  // 引用传参
  if (!p) p = ++cnt;  // 当结点为空时，创建一个新的结点
  if (s == t) {
    sum[p] += f;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (x <= m)
    update(ls[p], s, m, x, f);
  else
    update(rs[p], m + 1, t, x, f);
  sum[p] = sum[ls[p]] + sum[rs[p]];  // pushup
}

// 用法：query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r) {
  if (!p) return 0;  // 如果结点为空，返回 0
  if (s >= l && t <= r) return sum[p];
  int m = s + ((t - s) >> 1), ans = 0;
  if (l <= m) ans += query(ls[p], s, m, l, r);
  if (r > m) ans += query(rs[p], m + 1, t, l, r);
  return ans;
}

没啥可说了。

线段树合并

两棵结构相同的线段树可以直接进行合并。

用两个指针 \(p\) 和 \(q\)，同步遍历两棵树。

若 \(p\) 或 \(q\) 为空，那么非空的那个作为合并后的节点。
否则将 \(q\) 的信息合并到 \(p\)，遍历左右儿子然后pushup。

void merge(int& p,int q,int l=1,int r=n) {
	if(!p||!q) { p|=q; return; }
	if(l==r) {
		// 合并叶子节点
		return;
	}
	int mid=(l+r)>>1;
	merge(ls[p],ls[q],l,mid);
	merge(rs[p],rs[q],mid+1,r);
	pushup(p);
}

复杂度？

~~我不会证~~。

luogu3224 永无乡

板子题，并查集维护连通块，顺便进行合并，查询的时候全局线段树上二分即可。

luogu3201 梦幻布丁

每种颜色开一棵线段树，叶子为 \(1\) 表示这个位置的颜色是它。那么这棵线段树对答案的贡献就是连续 \(1\) 段的段数。记录区间左右端点的颜色，容易维护。

合并两种颜色就相当于合并这两棵线段树，对答案的影响显然与其它颜色段无关，随便搞一下就完了。

标记永久化

通过摒弃下传标记来降低常数。

遇到一个被完全覆盖的区间直接打标记
否则直接通过这个区间与操作区间的交修改区间信息
查询的时候加上标记

下面给出区间加法的代码。

void modify(int L,int R,int d,int x=1,int l=1,int r=n) {
    if(L<=l&&r<=R) { tag[x]+=d; return; }
    int mid=(l+r)>>1;
    if(L<=mid) modify(L,R,d,x<<1,l,mid);
    if(R>mid)  modify(L,R,d,x<<1|1,mid+1,r);
    pushup(x);
}
int query(int L,int R,int x=1,int l=1,int r=n) {
    if(L<=l&&r<=R) return t[x]+tag[x]*(r-l+1);
    int mid=(l+r)>>1, ans=tag[x]*(min(R,r)-max(L,l)+1);
    if(L<=mid) ans+=query(L,R,x<<1,l,mid);
    if(R>mid)  ans+=query(L,R,x<<1|1,mid+1,r);
    return ans;
}