主席树查询区间第K大本质是二分权值+前缀差分计数：先离散化并构建权值线段树的前缀版本，再通过root[r]−root[l−1]获取区间权值频次，最后在值域上二分——比较左子树区间计数left_cnt与k决定走向。
主席树查询区间第K大本质是二分权值 + 前缀差分计数
主席树本身不直接支持“区间第K大”，而是靠构建权值线段树的前缀版本，再利用两个历史版本相减得到区间内各权值的出现次数。查询时在权值线段树上模拟二分：往左走还是往右走，取决于左子树在该区间内的总出现次数是否 ≥ K。
关键点在于：不是对下标二分，而是对离散化后的权值范围二分；每次比较的是 left_cnt = tr[tr[r].l].cnt - tr[tr[l].l].cnt，即区间 [l, r] 中落在当前左子树权值范围内的数的个数。
建树前必须离散化，且要保留所有可能查询的权值
原始数组中没出现的数，也可能成为第K大的候选（比如查询 [1,3] 第2大，而数组是 [1,5,10]，答案是5 —— 它在离散化数组里必须有位置）。漏掉会导致 query 走到空节点或 cnt 不匹配。
- 用
std::vector收集所有原数组元素，再std::sort+std::unique去重 - 离散化映射用
std::lower_bound，别手写二分出界 - 建树时
build(1, n)的 n 是离散化后大小，不是原数组长度
query 函数参数和递归逻辑容易写反
常见错误是把版本号传错（比如用 root[l] 和 root[r] 直接相减，但主席树要求的是 root[r] − root[l-1]），或者在递归时左右子树版本号没同步更新。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
标准 query 签名应为：int query(int u, int v, int l, int r, int k)，其中 u 对应 root[l-1]，v 对应 root[r]，[l, r] 是当前权值线段树的值域范围（非原数组下标）。
递归分支判断逻辑：
int left_cnt = tr[tr[v].l].cnt - tr[tr[u].l].cnt;
if (k <= left_cnt) {
return query(tr[u].l, tr[v].l, l, mid, k);
} else {
return query(tr[u].r, tr[v].r, mid+1, r, k - left_cnt);
}空间和初始化不注意会 RE 或结果错
主席树节点数 ≈ n * log(max_val)，离散化后 max_val 是去重后大小，通常 ≤ n，所以总节点数控制在 20 * n 比较安全（n ≤ 2e5 时开 4e6 节点）。别用 vector 动态 push_back 而不 reserve，也别把 cnt 初始化成 0 以外的值。
- 每个新节点必须显式设置
cnt = 0、l = r = 0 -
root[0]是空树，必须调用build构造（或直接赋零节点） - 如果用数组模拟指针，
tot从 1 开始，root[i]存的是节点下标，不是指针
最常被忽略的是：查询第K大 ≠ 第K小，得把 k 替换为 区间长度 - k + 1，或者建树时按降序离散化 —— 但更稳妥的做法是在查完第K小后，用 len - k + 1 转换，别在树结构里硬改顺序。
