Home Archives Tags Friends About
学习笔记：树套树
2025-10-07

第一次学树套树时，并没有什么特别的感觉，因为属于我的离线分治，我早已遇见

并非第一次学

线段树

  • 考虑线段树的本质，即给定序列，能够返回关键字在 \([l,r]\) 内的可加信息之和
  • 仅需要保证信息是可加的（如众数，mex 等显然不在此列）

树状数组

  • 给定序列，能够返回任意关键字处的前缀和 / 后缀和，需要保证信息是可加的
  • 如果要求任意区间内关键字的信息之和，会用到差分，此时还需额外保证信息是可减的（如 min / max 显然不在此列）

主席树 / 可持久化线段树

之前有人在争论『主席树』是否等价于『可持久化线段树』，其实从当前 OI 环境的语境下我觉得是等价的

  • 给定序列，存在关键字 A 和关键字 B，能够求出 \(([0, A'], [B_1, B_2])\) 这个矩形的信息和（这里的矩形可能是 DAG 状的）

    也就是说主席树本身存的是关于 A 的信息前缀和

  • 要求 A 只能来源于先前的 A（即 A 具有单调性），且底层信息的 delta 为 1

    需要发现这个条件是相当苛刻的，所以这里的 A 通常以时间 / 版本 / DAG 的形式出现

  • 如果信息具有可减性，对于 \(A_2\) 和其某个祖先 \(A_1\)，能够求出 \(([A_1,A_2],[B_1,B_2])\) 这个矩形的信息和。

  • 考虑为什么主席树不能解决三维偏序
  • 现在已经对关键字 C 排完序了，我们需要求出 \(([0, A], [0, B])\) 这个矩形的信息和
  • 发现 A 是不具备单调性的，有没有什么 DS 能够不要求 A 的单调性呢？

树状数组套线段树

  • 用 \(n\) 棵线段树维护 B 的偏序关系，用类主席树的方式来排列这些树

  • 发现一次修改需要改一段后缀

    这一点我们前面说过了，主席树本身存储的是 A 维的前缀和。

  • 所以直接解决这个问题：维护信息的差分。这样就可以通过询问前缀得到原始信息

  • 这个结构和树状数组是很吻合的，考虑在树状数组的每个点上维护动态开点线段树

    这样就可以只用修改 log 个线段树

  • 考虑怎么询问

    我最初的想法是，做一个线段树合并，利用 DS 本身的树形结构可以有一个 dsu on tree 的复杂度（即 \(O(nq\log^2 n)\)），但显然这个太糖了

    正常的做法是，注意到每个点的权值线段树结构相同，所以在 log 个线段树上同时维护，当作包含长度 log 的数组的结构体即可

  • 同树状数组，要求信息有可减性

  • 但由于外层的 DS 本质上舍弃了主席树 DAG 的结构

    导致不能直接简单用于树上问题，而是需要在 DFS 序上作文章

  • 实际上常数很大，超过 \(10^5\) 就不太能跑得动了

Dynamic Rankings / K大数查询

https://www.luogu.com.cn/problem/P2617 / https://www.luogu.com.cn/problem/P3332

  • 全局第 \(k\) 大就是普通的权值线段树上二分，抑或平衡树，抑或 01-Trie（三者等价）
  • 这里的权值线段树上二分，其实是矩形第二维限制的变体
  • 发现这里只需要简单地维护元素个数，是具有可减性的。

三维偏序（陌上花开）

https://www.luogu.com.cn/problem/P3810

  • 树状数组套权值线段树即可

二逼平衡树

https://loj.ac/p/106

  • 和 k 大数差不多，都是权值线段树那些东西

网络管理

https://www.luogu.com.cn/problem/P4175

维护带修树上简单路径第 \(k\) 大。

  • 做树上差分即可转化为序列第 \(k\) 大。

买宝石

https://www.becoder.com.cn/contest/6620/problem/4

给定根为 \(1\) 的树，每个点 \(u\) 上有 \(k_u\) 个价钱为 \(w_u\) 的物品，可以在时间 \(t_u\) 及之后获得

给定 \(Q\) 次询问，从问 \(x\) 出发到根的路径上所有在时刻 \(T\) 可以获得的物品全部拿出来排成一列，拥有 \(K\) 金钱时，按照价值从小到大购买，买到的最后一个物品价值。

\(n\le 10^5\)，价钱：\(10^{15}\)，时间：\(10^5\)，个数：\(10^5\)。

  • 信息自带一个有序的时间偏序维 \(T\) 且原生有序，所以不能整体二分，必须处理 \(k\) 偏序维和 \(w\) 二分维。
  • 总的来说，就是维护了两个关键字，或者说一个矩形
  • 根据在 A，B 维需要做的操作选择，以及需要维护的信息类型，选择相应的数据结构

关于整体二分

  • 考虑动态区间第 K 大这一类的问题，特征是 A 维『求和』，B 维二分
  • 此时可以把对 B 维的二分提到外层一起进行，反过来对 A 维应用数据结构
  • 考虑到树套树常数过大，所以在能用整体二分的时候不推荐用树套树

言论