网站单向外链推广工具,网络文化经营许可证有效期,怎样建设有价值的网站,中山做网站做的好的公司今天给大家带来的是关于主席树的学习#xff0c;主席树是在线段二分的基础上优化空间复杂度#xff0c;同时注意树中存储的是权值个数#xff0c;这点区分于传统线段树#xff0c;主席树的内容比较复杂#xff0c;希望能对你有所帮助。1.权值线段树2.主席树#xff1a;题…今天给大家带来的是关于主席树的学习主席树是在线段二分的基础上优化空间复杂度同时注意树中存储的是权值个数这点区分于传统线段树主席树的内容比较复杂希望能对你有所帮助。1.权值线段树2.主席树题目描述给定一个长度为 N 的数组 a其初值分别为 a1,a2,...,aN。现有 Q 个查询查询格式形如l r k。对于每个查询要求你回答 al,al1,...,ar 区间内第 k 小的元素为多少。输入描述输入第 1行包含两个正整数 N,Q分别表示数组 a的长度和查询的个数。第 2 行包含 N个非负整数 a1,a2,...,aN表示数组 a元素的初值。第 3∼Q−2 行每行包含三个正整数 l,r,k表示查询al,al1,...,ar 区间内的第 k 小值。1≤N,Q≤2×1051≤l≤r≤N1≤k≤r−l1−109≤ai≤109。输出描述输出共 Q行每行包含一个整数表示相应查询的答案。输入案例
5 5
1 2 3 4 5
1 2 1
1 3 2
2 5 3
3 4 1
1 5 5输出案例
1
2
4
3
5代码部分
#include bits/stdc.h
#define int long long
using namespace std;
const int N 2e5 9;
int n, q;
vectorint X;
int getidx(int x)
{return lower_bound(X.begin(), X.end(), x) - X.begin() 1;
}
int a[N], root[N];
struct Node{int val, ls, rs;
}t[N * 30];
int tot 0;
void pushup(int o)
{t[o].val t[t[o].ls].val t[t[o].rs].val;
}void update(int o, int pre, int val, int s 1, int e n)
{o tot;t[o] t[pre];if(s e){t[o].val ;return ;}int mid (s e) 1;if(val mid) update(t[o].ls, t[pre].ls, val, s, mid);else update(t[o].rs, t[pre].rs, val, mid 1, e);pushup(o);
}int query(int lo, int ro, int k, int s 1, int e n)
{if(s e){return s;}int mid (s e) 1;int leftsum t[t[ro].ls].val - t[t[lo].ls].val;if(k leftsum) return query(t[lo].ls, t[ro].ls, k, s, mid);else return query(t[lo].rs, t[ro].rs, k - leftsum, mid 1, e);
}signed main()
{cin n q;for(int i 1; i n; i){cin a[i];X.push_back(a[i]);}sort(X.begin(), X.end());X.erase(unique(X.begin(), X.end()), X.end());for(int i 1; i n; i){update(root[i], root[i - 1], getidx(a[i]));}while(q --){int l, r, k; cin l r k;cout X[query(root[l - 1], root[r], k) - 1] endl;}return 0;
}注意点⚠️一、问题本质与核心难点1. 问题本质给定静态数组无修改操作多次查询区间[l, r]内的第 k 小元素。例如数组[3,1,4,2]查询[1,4,2]区间 [1,4] 的第 2 小答案为 2。2. 核心难点数据规模大N, Q ≤ 2e5暴力解法每次排序区间时间复杂度O(Q*N log N)必然超时。元素值域广a[i] ∈ [-1e9, 1e9]无法直接用元素值作为线段树的下标空间会爆炸。因此需要解决两个关键问题① 如何高效处理区间查询② 如何压缩元素值域以节省空间。二、第一步离散化 —— 压缩值域离散化是处理 “大值域、小数量” 问题的经典技巧核心是将原始元素映射到连续的小整数区间不改变元素的相对大小关系。1. 离散化的必要性主席树需要用 “元素值” 作为线段树的 “区间范围”统计每个值的出现次数。若直接用[-1e9, 1e9]作为线段树的区间需要4*2e9个节点空间完全无法承受。而数组中最多只有2e5个不同元素离散化后可将值域压缩到[1, 2e5]空间开销骤降。2. 离散化的具体步骤对应代码中的实现假设原始数组a [3, 1, 4, 2, 1]离散化过程如下步骤 1收集所有元素去重排序收集数组元素到临时数组XX [3,1,4,2,1]排序并去重sort(X.begin(), X.end()) → [1,2,3,4]X.erase(unique(X.begin(), X.end()), X.end()) → [1,2,3,4]unique函数将重复元素移到数组末尾返回不重复部分的尾指针erase函数删除重复部分得到不重复的有序数组。步骤 2建立 “原始值→离散值” 的映射用lower_bound找到原始值在X中的位置作为离散值通常从 1 开始方便线段树索引函数getidx(x)return lower_bound(X.begin(), X.end(), x) - X.begin() 1lower_bound返回第一个≥x 的元素的迭代器减去X.begin()得到下标0-based加 1 转为 1-based 离散值。示例映射3 → 下标 2 → 离散值 31 → 下标 0 → 离散值 14 → 下标 3 → 离散值 42 → 下标 1 → 离散值 2。3. 离散化的关键性质离散后的值保留了原始值的相对大小若a b则getidx(a) getidx(b)。这是后续用线段树统计 “第 k 小” 的基础。三、第二步主席树 —— 可持久化的线段树主席树的核心是 **“每次更新只新建受影响的节点复用未修改的节点”**从而保留数组每个前缀的线段树状态即root[i]表示前i个元素构成的线段树的根节点。1. 主席树的节点结构对应代码中的struct Node
struct Node{int val; // 该节点对应的区间内元素的出现次数int ls, rs; // 左子树、右子树的节点编号线段树是动态构建的用编号索引节点
}t[N * 30]; // 节点池N*30是经验值足够容纳2e5个前缀的线段树
int tot 0; // 节点计数器记录已创建的节点总数2. 核心操作 1更新update函数—— 构建前缀线段树update函数的作用是基于前i-1个元素的线段树根节点pre插入第i个元素的离散值得到前i个元素的线段树根节点o。操作逻辑以插入离散值val为例
void update(int o, int pre, int val, int s 1, int e n)
{o tot; // 1. 新建当前节点复用前一个树的节点只修改受影响的分支t[o] t[pre]; // 2. 复制前一个树的节点信息未修改的分支直接复用if(s e) // 3. 到达叶子节点对应离散值val的区间{t[o].val ; // 4. 叶子节点的计数1该离散值的出现次数增加return ;}int mid (s e) 1; // 5. 拆分区间为左[s, mid]、右[mid1, e]if(val mid) update(t[o].ls, t[pre].ls, val, s, mid); // 6. 若val在左区间递归更新左子树else update(t[o].rs, t[pre].rs, val, mid 1, e); // 7. 若val在右区间递归更新右子树pushup(o); // 8. 回溯更新当前节点的计数左子树计数右子树计数
}关键为什么要 “复用节点”每次更新只新建O(log M)个节点M 是离散化后的值域大小约 2e5log M≈20n 次更新共新建O(n log M)个节点空间复杂度O(n log M)完全可承受。3. 核心操作 2查询query函数—— 求区间第 k 小查询[l, r]的第 k 小本质是计算 “前 r 个元素的线段树” 与 “前 l-1 个元素的线段树” 的差值得到区间[l, r]内的元素分布再通过二分查找定位第 k 小。差值的含义线段树的每个节点val表示 “对应区间内的元素出现次数”t[root[r]].val - t[root[l-1]].val区间[l, r]内该节点对应的值域区间的元素总数。4.深刻理解主席树的含义与意义在主席树中val 并不是 “元素的个数”而是离散化后的元素值即元素在值域中的位置。这里的 val mid 比较本质是在按 “值域区间” 划分线段树的左右子树这与普通线段树按 “下标区间” 划分的逻辑不同但核心思想一致 —— 都是通过二分法缩小查询范围。一、先明确主席树的线段树是 “值域线段树”普通线段树如区间求和 / 最大值通常是按 “数组下标区间” 划分例如左子树管 [l, mid]右子树管 [mid1, r]节点存储的是 “该下标区间内的统计信息”。而主席树中的线段树是按 “元素值域区间” 划分例如左子树管 [s, mid]右子树管 [mid1, e]其中 s 和 e 是离散化后的最小值和最大值例如 [1, M]M 是不同元素的个数。节点存储的是 “该值域区间内的元素出现次数”。因此val 是离散化后的元素值属于 [1, M] 中的某个值mid 是当前值域区间的中点val mid 的含义是 “判断当前元素属于左半值域还是右半值域”。二、举例理解值域线段树的划分逻辑以 a [3, 1, 4, 2, 1] 为例离散化后的值域为 [1, 4]对应原始值 [1, 2, 3, 4]构建值域线段树的过程如下根节点管辖区间 [1, 4]表示离散值 1~4 的范围mid (14)/2 2。左子树管辖区间 [1, 2]离散值 1 和 2右子树管辖区间 [3, 4]离散值 3 和 4。插入元素 a[1] 3离散值 val3根节点判断 3 2否 → 进入右子树[3,4]。右子树的 mid (34)/2 3判断 3 3是 → 进入其左子树[3,3]。到达叶子节点 [3,3]将该节点的计数 1表示离散值 3 出现了 1 次。插入元素 a[2] 1离散值 val1根节点判断 1 2是 → 进入左子树[1,2]。左子树的 mid (12)/2 1判断 1 1是 → 进入其左子树[1,1]。到达叶子节点 [1,1]计数 1离散值 1 出现了 1 次。三、为什么要按 “值域” 划分因为主席树的核心功能是查询 “第 k 小元素”而 “第 k 小” 本质是按元素的值的大小排序后的结果。按值域划分线段树能直接统计 “小于等于某个值的元素有多少个”从而通过二分快速定位第 k 小。例如查询区间 [1,5] 的第 3 小根节点统计左值域 [1,2] 的元素总数为 3离散值 1 出现 2 次 离散值 2 出现 1 次第 3 小刚好在左值域内因此递归左子树继续查找最终定位到离散值 2对应原始值 2。5.lo与ro和root之间的关系一、ro 和 lo 的含义查询阶段在查询函数 query(int lo, int ro, int k, ...) 中ro 是 root[r] 的缩写表示 “前 r 个元素构成的线段树的根节点”即包含数组 a[1..r] 所有元素的版本。lo 是 root[l-1] 的缩写表示 “前 l-1 个元素构成的线段树的根节点”即包含数组 a[1..l-1] 所有元素的版本。关键作用通过 “版本差值” 计算区间 [l, r] 的元素分布主席树的查询核心是 “用后一个版本减去前一个版本”得到区间 [l, r] 的信息t[ro].ls 是 root[r] 对应线段树的左子节点t[lo].ls 是 root[l-1] 对应线段树的左子节点leftsum t[t[ro].ls].val - t[t[lo].ls].val 表示区间 [l, r] 中落在左子树对应的值域区间内的元素总个数。例如
root[5] 包含 a[1..5] 的元素root[1] 包含 a[1..1] 的元素两者的差值就是 a[2..5] 的元素分布。二、root 数组的含义与赋值构建阶段root 数组是 “版本管理器”存储了每个前缀的线段树的根节点编号其赋值过程隐含在 update 函数中。1. root 数组的初始化与赋值初始状态root[0] 是 “空树”默认值为 0对应节点池中的空节点。迭代赋值通过 update(root[i], root[i-1], getidx(a[i])) 实现root[i-1] 是 “前 i-1 个元素的线段树根节点”上一个版本update 函数基于 root[i-1] 插入第 i 个元素生成新的根节点 root[i]当前版本最终 root[i] 存储的是 “前 i 个元素构成的线段树的根节点编号”。例如root[1] 是插入 a[1] 后的版本root[2] 是在 root[1] 基础上插入 a[2] 后的版本以此类推。2. root 数组的关键作用保存历史版本每个 root[i] 对应一个 “前缀线段树”记录了 a[1..i] 的元素分布实现了 “可持久化”保留所有历史状态。支持区间查询通过 root[r] 和 root[l-1] 的差值快速得到 a[l..r] 的元素分布无需重新构建区间线段树。三、整体逻辑串联以具体例子为例假设数组 a [3,1,4,2,1]n5构建阶段root[0] 0空树root[1]基于 root[0] 插入 3离散值 3得到包含 [3] 的线段树root[2]基于 root[1] 插入 1离散值 1得到包含 [3,1] 的线段树... 以此类推root[5] 包含 [3,1,4,2,1] 的所有元素。查询阶段例如查询 l2, r5, k2lo root[1]包含 [3]ro root[5]包含 [3,1,4,2,1]计算差值[3,1,4,2,1] - [3] [1,4,2,1]即区间 [2,5] 的元素通过 query(lo, ro, 2) 找到该区间的第 2 小元素结果为 1。好了今天的分享就到这里希望能对你有所帮助。
