主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
树套树 - 线段树套平衡树（Segment + FHQ-Treap）
最后更新于 2025-07-31 11:06:39
作者
yuanzhiteng
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
思想很简单，就是线段树上的每一个点都维护的都不在是一个区间，而是一棵平衡树。 具体地，每一个点都维护那一个点上平衡树的根。 但是代码实在是难写，常数巨大，洛谷还卡常，卡了老久才过。 细节超多，在代码中了。 时间复杂度： 区间查一个数的排名：$\mathcal{O}(\log ^2n)$。 区间查对应排名的数：$\mathcal{O}(\log ^3n)$。（线段树上二分实现） 单点修改：$\mathcal{O}(\log ^2n)$。 区间查一个数的前驱/后继：$\mathcal{O}(\log ^2n)$。 总时间复杂度：$\mathcal{O}(m\log ^3n)$。 [例题](https://www.luogu.com.cn/problem/P3380) ```cpp #include <iostream> //线段树套平衡树(Segment + FHQ-Treap),O(mlog^{3}n).常数巨大 #include <stdio.h> #include <algorithm> #include <string.h> #include <random> #include <ctime> using namespace std; const int maxn = 5e4 + 5; const int maxnn = 2e6 + 5; //由于一直在删点加点,平衡树数组的大小要往大了开 const int inf = 2147483647; mt19937 rnd(time(0)); template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f; } template <typename T, typename... Args> inline void read (T &x, Args&... Arg) { read (x), read (Arg...); } int n,m; int a[maxn]; int mina = inf,maxa; int tot; struct Treap{ //FHQ-Treap struct Treap_tree{ int sz,rnk,key,lson,rson,num,own; }tree[maxnn]; inline int newnode(int x){ tree[++tot].rnk = rnd(); tree[tot].num = tree[tot].own = tree[tot].sz = 1; tree[tot].key = x; return tot; } inline void push_up(int root){ tree[root].sz = tree[tree[root].lson].sz + tree[tree[root].rson].sz + 1; tree[root].num = tree[tree[root].lson].num + tree[tree[root].rson].num + tree[root].own; } inline int merge(int root1,int root2){ if(!root1) return root2; if(!root2) return root1; if(tree[root1].rnk < tree[root2].rnk){ if(tree[root2].key < tree[root1].key) tree[root1].lson = merge(tree[root1].lson,root2); else tree[root1].rson = merge(tree[root1].rson,root2); push_up(root1); return root1; } else{ if(tree[root1].key < tree[root2].key) tree[root2].lson = merge(tree[root2].lson,root1); else tree[root2].rson = merge(tree[root2].rson,root1); push_up(root2); return root2; } } inline pair<int,int> split(int root,int cut){ pair<int,int>ret; if(!root){ ret.first = 0; ret.second = 0; return ret; } if(tree[root].key <= cut){ ret = split(tree[root].rson,cut); tree[root].rson = ret.first; ret.first = root; push_up(root); } else{ ret = split(tree[root].lson,cut); tree[root].lson = ret.second; ret.second = root; push_up(root); } return ret; } inline void Add(int &root,int x){ //要将线段树中这个点上平衡树对应的root传址 pair<int,int>tmpl,tmpr; tmpr = split(root,x); tmpl = split(tmpr.first,x-1); if(tmpl.second == 0) tmpl.second = newnode(x); else{ tree[tmpl.second].own++; push_up(tmpl.second); } root = merge(merge(tmpl.first,tmpl.second),tmpr.second); } inline void Delete(int &root,int x){ pair<int,int>tmpl,tmpr; tmpr = split(root,x); tmpl = split(tmpr.first,x-1); if(tree[tmpl.second].own == 1) root = merge(tmpl.first,tmpr.second); else{ tree[tmpl.second].own--; push_up(tmpl.second); root = merge(merge(tmpl.first,tmpl.second),tmpr.second); } } inline int query_rank(int root,int x){ //查排名-1的值,即严格小于x的个数.(因为线段树上会多次累加,所以不能直接查排名)为了卡常,直接递归去找,而不去split再merge. if(!root) return 0; int lson = tree[root].lson , rson = tree[root].rson; if(tree[root].key == x) return tree[lson].num; if(x < tree[root].key) return query_rank(lson,x); else return tree[lson].num + tree[root].own + query_rank(rson,x); } inline int query_pre(int &root,int x){ //查前驱 pair<int,int>tmp = split(root,x-1); int now = tmp.first; if(!now) return -inf; while(tree[now].rson) now = tree[now].rson; int ret = tree[now].key; root = merge(tmp.first,tmp.second); return ret; } inline int query_back(int &root,int x){ //查后继 pair<int,int>tmp = split(root,x); int now = tmp.second; if(!now) return inf; while(tree[now].lson) now = tree[now].lson; int ret = tree[now].key; root = merge(tmp.first,tmp.second); return ret; } }treap; struct Segment{ //Segment_Tree int tree[maxn << 2]; //tree存当前线段树节点对应的平衡树的root inline int left(int x){ return x << 1; } inline int right(int x){ return x << 1 | 1; } inline void build(int p,int l,int r){ if(l == r){ tree[p] = treap.newnode(a[l]); //创立一个新的节点 return; } for(int i=l;i<=r;i++) treap.Add(tree[p],a[i]); //暴力插入,同时更新了tree[i].root int mid = (l + r) >> 1; build(left(p),l,mid); build(right(p),mid + 1,r); } inline int query_rank(int p,int l,int r,int dl,int dr,int x){ //查询区间[dl,dr]内x的排名 if(dl <= l && dr >= r) return treap.query_rank(tree[p],x); //直接去平衡树内查找 int mid = (l + r) >> 1,ret = 0; if(dl <= mid) ret += query_rank(left(p),l,mid,dl,dr,x); if(dr > mid) ret += query_rank(right(p),mid + 1,r,dl,dr,x); return ret; } inline void update(int p,int l,int r,int pos,int x){ //将pos处的权值修改为x treap.Delete(tree[p],a[pos]); treap.Add(tree[p],x); //先在平衡树中删除,再添加.注意一路上都要修改,这样就不用push_up了 if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) update(left(p),l,mid,pos,x); else update(right(p),mid + 1,r,pos,x); } inline int query_pre(int p,int l,int r,int dl,int dr,int x){ //查询区间[dl,dr]内x的前驱 if(dl <= l && dr >= r) return treap.query_pre(tree[p],x); int mid = (l + r) >> 1; int ret = -inf; if(dl <= mid) ret = max(ret,query_pre(left(p),l,mid,dl,dr,x)); if(dr > mid) ret = max(ret,query_pre(right(p),mid + 1,r,dl,dr,x)); return ret; } int query_back(int p,int l,int r,int dl,int dr,int x){ //查询区间[dl,dr]内x的后继 if(dl <= l && dr >= r) return treap.query_back(tree[p],x); int mid = (l + r) >> 1; int ret = inf; if(dl <= mid) ret = min(ret,query_back(left(p),l,mid,dl,dr,x)); if(dr > mid) ret = min(ret,query_back(right(p),mid + 1,r,dl,dr,x)); return ret; } inline int query_kth(int l,int r,int k){ //查询区间[l,r]内排名为k的数,二分查找 int L = mina,R = maxa,mid; //卡二分上下界 int ret = 0; while(L <= R){ mid = (L + R) >> 1; if(query_rank(1,1,n,l,r,mid) + 1 <= k){ //别忘了query_rank查到的是严格小于mid的个数,所以排名的话要+1 L = mid + 1; ret = mid; } else R = mid - 1; } return ret; } }seg; int main(){ read(n,m); for(int i=1;i<=n;i++) read(a[i]),mina = min(mina,a[i]),maxa = max(maxa,a[i]); seg.build(1,1,n); int op; while(m--){ read(op); if(op == 1){ //query_rank int l,r,k; read(l,r,k); printf("%d\n",seg.query_rank(1,1,n,l,r,k) + 1); //别忘了+1 } else if(op == 2){ //query_kth int l,r,k; read(l,r,k); printf("%d\n",seg.query_kth(l,r,k)); } else if(op == 3){ //update int pos,k; read(pos,k); seg.update(1,1,n,pos,k); a[pos] = k; //这里也别忘了更新 maxa = max(maxa,k); mina = min(mina,k); } else if(op == 4){ //query_pre int l,r,k; read(l,r,k); printf("%d\n",seg.query_pre(1,1,n,l,r,k)); } else{ //query_back int l,r,k; read(l,r,k); printf("%d\n",seg.query_back(1,1,n,l,r,k)); } } return 0; } ``` 总结： 静态全局第 $k$ 小：$sort......$ 动态全局第 $k$ 小：**值域线段树 / 平衡树**。 静态区间第 $k$ 小：**主席树 / 整体二分**。 动态区间第 $k$ 小：**整体二分 / 树套树**。
正在渲染内容...
点赞
1
收藏
0
