【板子】权值线段树

一、概念1. 什么是权值线段树权值线段树 以数值为下标建立的线段树每个节点维护落在这个值区间内的元素的某种聚合信息。普通线段树的下标是第几个位置权值线段树的下标是数值本身。线段树需要支持单点修改但是不能插入新点权值线段树可以把不变的值开成点把变化的点数开成值本质上是线段树把值作为下标把点数作为原值把插入点变成单点修改。对比项普通线段树权值线段树下标含义数组位置i元素的值x叶子节点a[i]的值值为x的元素个数或其他信息节点含义区间[l,r]的聚合和/最值值在[l,r]范围内的聚合典型问题区间求和、区间修改第 k 小、排名、值域计数、值域最值2. 直观理解想象把数轴上每个整数位置都放了一个桶桶x里装的是值为x的元素有多少个权值线段树就是把这些桶按线段树结构组织起来可以快速往桶里加东西 / 拿走东西单点修改问一段连续的桶里总共有多少东西区间查询找第 k 个非空的桶二分查找3. 为什么需要离散化权值线段树的下标就是值本身。如果值域是 [−10e7,10e7] 或甚至10e18直接开数组不可能。解决方法把所有会用到的值收集起来排序去重用排名代替原值。原值3, 100000, -50, 3, 999 排序去重-50, 3, 999, 100000 映射 -50 → 1 3 → 2 999 → 3 100000 → 4这样值域就从 1018 压缩到了 m≤n最多 2×10e5线段树轻松开得下。如果值域本身就很小比如 ≤10e6可以跳过离散化直接用原值当下标。二、面向题型信号说明求第 k 小 / 第 k 大经典的 kth 操作求 x 的排名查比 x 小的有多少个求前缀/后缀中满足某个值域条件的数量区间sum找前面/后面第一个比 x 大的数前驱/后继转移条件涉及值域范围 [L,R] 内的最优值值域最值查询值域很大但操作次数不多离线离散化 or 动态开点经典题型题型 1平衡树替代品排名 / 第 k 小 / 前驱 / 后继典型题洛谷 P3369【模板】普通平衡树操作需求权值线段树做法插入 xadd(id(x), 1)删除 xadd(id(x), -1)排名x 是第几小sum(1, id(x)-1) 1第 k 小kth(k)前驱 x 的最大数kth(sum(1, id(x)-1))后继 x 的最小kth(sum(1, id(x)) 1)题型 2值域计数逆序对 / 区间统计典型题求逆序对、P1972 HH的项链思路从左到右扫描数组每遇到一个数 ai​查询值域 [ai​1,maxVal] 里已经有多少个数 → 就是 ai​ 产生的逆序对数量然后把 ai​ 插入权值线段树for (int i 1; i n; i) { ans seg.sum(a[i] 1, m); // 前面比 a[i] 大的个数 seg.add(a[i], 1); // 插入 a[i] }题型 3值域最值维护DP 优化 / 贪心典型题就是你之前问的那道最长 2x~3x 合法子序列思路权值线段树不存个数而是存某个值范围内元素的 DP 值最小值/最大值。操作做法插入update(id(x), dp_val)—— 用min/max更新查询query(L, R)—— 返回区间内的最值题型 4离线区间第 k 小主席树前置典型题P3835 静态区间第 k 小思路按原数组顺序每个位置建一个版本的权值线段树前缀和用可持久化线段树主席树实现查询[l, r]的第 k 小 第r版减去第l-1版后做kth这是权值线段树的高级应用知道思路即可板子不在本节范围。题型 5扫描线 权值线段树典型题CF 652D Nested Segments数每个区间包含多少个其他区间思路按右端点排序从左到右扫描权值线段树下标是左端点的值每遇到一个区间[L, R]查询值域[L, R]内已有多少个区间 → 就是答案然后把当前区间的左端点插入树中题型 6动态维护中位数 / 数据流第 k 大思路始终保持左右两棵权值线段树或用一棵 总数计数插入后调整两边数量差不超过 1中位数就是某一边的kth三、板子 板子 1基础计数通用覆盖题型 1/2/5struct WeightSegTree { int n; vectorint t; // 初始化m 是离散化后的值域大小 void init(int m) { n 1; while (n m) n 1; t.assign(2 * n, 0); } // 单点加 delta插入 1删除 -1 void add(int p, int delta) { int x p n - 1; t[x] delta; for (x 1; x; x 1) t[x] t[x 1] t[x 1 | 1]; } // 区间求和值域在 [l, r] 内共有多少个数 int sum(int l, int r) { if (l r) return 0; int res 0; l n - 1; r n - 1; while (l r) { if (l 1) res t[l]; if (!(r 1)) res t[r--]; l 1; r 1; } return res; } // 查第 k 小k 从 1 开始保证存在 int kth(int k) { int x 1; while (x n) { if (t[x 1] k) x x 1; else { k - t[x 1]; x x 1 | 1; } } return x - n 1; // 返回离散化后的编号 } // 以下是基于上面三个操作的封装 int rank(int id) { return sum(1, id - 1) 1; } // 值为 id 的排名 int pre(int id) { return kth(sum(1, id - 1)); } // 前驱的编号 int nxt(int id) { return kth(sum(1, id) 1); } // 后继的编号 };使用示例WeightSegTree seg; seg.init(m); // m 离散化后不同值的个数 seg.add(getId(42), 1); // 插入 42 seg.add(getId(17), 1); // 插入 17 seg.add(getId(99), 1); // 插入 99 seg.add(getId(42), -1); // 删除一个 42 int cnt seg.sum(getId(10), getId(50)); // 值在 [10, 50] 之间的有几个 int rnk seg.rank(getId(99)); // 99 排第几 int kth seg.kth(2); // 第 2 小的数的编号 int pr seg.pre(getId(99)); // 99 的前驱编号 int nx seg.nxt(getId(17)); // 17 的后继编号 cout getVal(kth) \n; // 编号还原成原值 板子 2值域最值版题型 3DP 优化专用templatetypename T, T INF_VAL struct WeightSegTreeMin { int n; vectorT t; void init(int m) { n 1; while (n m) n 1; t.assign(2 * n, INF_VAL); } // 在位置 p 用 val 更新最小值 void update(int p, T val) { if (val INF_VAL) return; int x p n - 1; if (t[x] val) return; // 不用更新 t[x] val; for (x 1; x; x 1) { T nv min(t[x 1], t[x 1 | 1]); if (nv t[x]) break; t[x] nv; } } // 查询值域 [l, r] 内的最小值 T query(int l, int r) { if (l r) return INF_VAL; T res INF_VAL; l n - 1; r n - 1; while (l r) { if (l 1) res min(res, t[l]); if (!(r 1)) res min(res, t[r--]); l 1; r 1; } return res; } }; // 使用 WeightSegTreeMinint, 1e9 seg; seg.init(m); seg.update(pos, dp_value); int best seg.query(L, R);如果要维护最大值把min换成maxINF_VAL换成-INF即可。使用示例WeightSegTreeMinint, 1e9 seg; seg.init(m); // 假设算完了长度为 len-1 的 DP seg.update(pos[5], dp[5][len-1]); // 把位置 5 的信息加入 seg.update(pos[8], dp[8][len-1]); // 把位置 8 的信息加入 // 现在处理位置 i3需要找值在 [2*a[3], 3*a[3]] 范围内的最小 dp 值 int best seg.query(L[3], R[3]); // 这就是 dp[3][len] 板子 3动态开点在线大值域无需离散化当你不能离线离散化比如强制在线、值域 1018 且不知道会插什么值时用动态开点。struct DynamicSegTree { struct Node { int ls, rs, cnt; // 左孩子、右孩子、计数 }; vectorNode nodes; int root, tot; DynamicSegTree() { nodes.push_back({0, 0, 0}); // 0 号节点做空节点 root 0; tot 0; } void update(int u, long long l, long long r, long long pos, int delta) { if (!u) { u tot; nodes.push_back({0, 0, 0}); } if (l r) { nodes[u].cnt delta; return; } long long mid (l r) 1; if (pos mid) update(nodes[u].ls, l, mid, pos, delta); else update(nodes[u].rs, mid 1, r, pos, delta); nodes[u].cnt nodes[nodes[u].ls].cnt nodes[nodes[u].rs].cnt; } int query(int u, long long l, long long r, long long ql, long long qr) { if (!u || ql r || qr l) return 0; if (ql l r qr) return nodes[u].cnt; long long mid (l r) 1; return query(nodes[u].ls, l, mid, ql, qr) query(nodes[u].rs, mid 1, r, ql, qr); } // 对外接口 void add(long long pos, int delta) { if (!root) root tot, nodes.push_back({0, 0, 0}); update(root, -1e18, 1e18, pos, delta); } int range_count(long long ql, long long qr) { return query(root, -1e18, 1e18, ql, qr); } };动态开点的代价是每个节点要手动管理左右孩子但空间从 O(4n) 变成了 O(操作次数×logV)使用示例DynamicSegTree seg; seg.add(42, 1); // 插入 42 seg.add(1000000000000000000LL, 1); // 直接插入 10^18不需要离散化 seg.add(42, -1); // 删除一个 42 int cnt seg.range_count(10, 100); // 值在 [10, 100] 内有几个 // cnt 0因为 42 被删了10^18 不在范围内四、复杂度操作时间复杂度空间复杂度建树O(m)O(m)单点修改O(logm)—区间查询O(logm)—kth 查询O(logm)—动态开点版O(logV)O(qlogV)其中 m 离散化后值域大小V 原始值域q 操作次数。