std::set和std::map因底层红黑树不支持O(log n)区间计数，需遍历导致最坏O(k)；而GNU PBDS的order_statistic_tree通过order_of_key实现O(log n)范围统计，如order_of_key(R+1)-order_of_key(L)。
为什么 std::set 和 std::map 不能直接做高效范围统计
因为它们底层是红黑树，支持 lower_bound 和 upper_bound，但不提供 O(log n) 的区间元素个数查询——你得手动遍历迭代器区间，最坏 O(k)（k 是范围内元素数），完全失去对数效率。
用 order_statistic_tree（GNU PBDS）实现 O(log n) 范围计数
GNU 扩展的 tree 容器带 order_of_key 和 find_by_order，能直接算出「小于某值的元素个数」，从而快速得出范围 [L, R] 内元素数： order_of_key(R+1) - order_of_key(L)。
实操要点：
- 必须开启
#include <ext></ext>和#include <ext></ext> - 模板参数要完整：键类型、空类型、比较函数、rb_tree_tag、
tree_order_statistics_node_update -
order_of_key(x)返回严格小于x的元素个数；若需闭区间 [L, R]，用order_of_key(R+1) - order_of_key(L)（注意 L/R 类型兼容性） - 重复元素？默认不允许多键；如需支持，改用
pair<key int></key>或切换到duplicate模式（需自定义节点更新）
示例：
立即学习“C++免费学习笔记（深入）”；
#include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ostree = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; ostree t; t.insert(5); t.insert(3); t.insert(7); int cnt = t.order_of_key(7) - t.order_of_key(3); // 得到 1（仅 5），[3,7) 左闭右开
自己写带子树大小的平衡 BST（如 treap）时的关键点
核心不是写平衡逻辑，而是维护每个节点的 size 字段（含自身 + 左右子树总节点数），并在所有旋转、插入、删除中同步更新。
范围统计逻辑依赖 count_less_than(x) 函数：
- 从根开始递归：若当前节点值
< x，则左子树全计入，加上当前节点，再向右子树查count_less_than(x) - 否则只向左子树查
- 每次递归只走一条路径，O(log n)
容易漏的细节：
- 插入/删除后必须从修改点向上回溯更新所有祖先的
size - 若支持重复值，
size应统计频次总和，而非 distinct count - 懒更新或批量操作时，
size维护极易出错——建议单元测试覆盖单点增删、区间插入、空树边界
别踩坑：浮点数、自定义类型与迭代器失效
order_of_key 对浮点数不安全——1.0 和 0.999999999 可能被不同精度判定为相等或不等，导致计数偏差。一律转整数缩放或用定点比较。
自定义类型必须严格满足 Strict Weak Ordering：若 a < b 和 b < a 都为 false，则 a == b；否则 order_of_key 行为未定义。
注意：PBDS tree 的迭代器在插入/删除时可能失效（不同于 std::set 的稳定迭代器），范围统计中不要混用迭代器遍历和 order_of_key 查询。
实际项目里，如果只是偶尔范围查询，用 std::vector + std::lower_bound + std::upper_bound 排序后二分更稳妥；真要高频动态范围统计，PBDS 是目前 C++ 最省力的选择——但得接受它非标准、跨平台风险和调试难度。
