DS Trick

Tangninghaha · 2025-01-10 07:51:32 · 算法·理论

元旦快乐！

题单

线段树分裂与合并

动态开点线段树

堆式线段树采用点 i 的左儿子为 2\times i，右儿子为 2\times i+1 的结构，很容易根据父亲找到儿子。但是对于节点较少的线段树，这样存储可能会浪费大量空间。

例如：

• 如果一棵线段树只有一条右链，即每个节点是父亲的右儿子，右链的叶子上存储了信息，那么这个节点的编号是 O(n) 级别的，然而树上有用节点只有 O(\log n) 个。

• 如果维护一棵值域是 10^{9} 的权值线段树，使用堆式建树有 O(V) 个节点，显然不可接受。然而每一次操作只会访问到 O(\log V) 个节点，在 q 次操作下，有用节点实际上只有 O(q\log v) 个。

上述两种情况说明，在堆式建树可能会产生无效节点。

不再认为点 i 的左儿子为 2\times i，右儿子为 2\times i+1，而是记录线段树上每一个节点的左右儿子的下标。初始根的左右儿子下标为 0。

当访问到一个标号为 0 的节点时，新建一个节点，将信息储存在这个节点，处理完之后返回这个新标号即可。

比如说单点修改可以这么写（将 p 的值改为 v）：

int chg(int p, int v, int id, int l, int r) {
  if (!id) id = ++cnt;
  if (l == r) {
    // update information
    return id;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) ls[id] = chg(p, v, ls[id], l, mid);
  else rs[id] = chg(p, v, rs[id], mid + 1, r);
  // merge ls[id] and rs[id]
  return id;
}

线段树合并

现在有两棵动态开点线段树，希望将两棵线段树的信息合并。

对于只有一棵线段树有信息的位置，将有信息的节点返回即可。对于两棵树均有信息的节点，递归合并两棵子树，再将两棵子树的信息合并。

假设有 T 个位置两棵树都有值，这样复杂度是 O(\text{T}) 的

int merge(int u, int v, int l, int r) {
  if (!u || !v) return u | v;
  if (l == r) {
    // merge information u and v to u
    return u;
  }
  int mid = (l + r) >> 1;
  ls[u] = merge(ls[u], ls[v], l, mid);
  rs[u] = merge(rs[u], rs[v], mid + 1, r);
  // merge ls[u] and rs[u]
  return u;
}

P4556 雨天的尾巴

Link

给定一棵 n 个节点的树，有 m 次操作，每一次操作在 (x,y) 的路径上放置一个类型为 z 的物品。求每一个位置最多放置的物品类型。

先随意定一个根。修改可以差分成：在 x 和 y 处加上一个物品 z，在 lca 处减去一个物品 z，在 fa_{lca} 处再减去一个物品 z，这样每一个点子树内的物品数量和就是原本这个点的物品数量。

暴力的想法是每一个位置开一个桶，记录每一种类型出现次数。这样无论是查询还是合并，复杂度都不可承受。

可以将桶换成动态开点的权值线段树，使用线段树合并进行维护。