关键词：
树套树
一种思想，就是一棵树的节点是另一颗树。
在外面的叫外层树，在里面的叫内层树。
外层树一般是， 树状数组 ， 线段树
内层树一般是 平衡树 ， STL , 线段树
线段树套STL
/*
* @Author: zhl
* @Date: 2020-11-16 12:50:32
*/
#include<bits/stdc++.h>
#define lo (o<<1)
#define ro (o<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N = 5e4 + 10, inf = 1e9;
multiset<int>s[N << 2];
int A[N];
void build(int o, int l, int r)
s[o].insert(inf); s[o].insert(-inf);
for (int i = l; i <= r; i++) s[o].insert(A[i]);
if (l == r)return;
build(lo, l, mid);
build(ro, mid + 1, r);
void updt(int o, int l, int r, int pos, int v)
s[o].erase(s[o].lower_bound(A[pos]));
s[o].insert(v);
if (l == r)return;
if (pos <= mid) updt(lo, l, mid, pos, v);
else updt(ro, mid + 1, r, pos, v);
int query(int o, int l, int r, int L, int R, int v)
if (L <= l and r <= R) return *prev(s[o].lower_bound(v));
int ans = -inf;
if (L <= mid)ans = max(ans, query(lo, l, mid, L, R, v));
if (R > mid) ans = max(ans, query(ro, mid + 1, r, L, R, v));
return ans;
int n, m;
int main()
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", A + i);
build(1, 1, n);
while (m--)
int op, a, b, x; scanf("%d", &op);
if (op == 1)
scanf("%d%d", &a, &b);
updt(1, 1, n, a, b);
A[a] = b;
else
scanf("%d%d%d", &a, &b, &x);
printf("%d
", query(1, 1, n, a, b, x));
线段树套平衡树
很多棵树的时候可以开一个 root 数组就可以，这样可以不需要传引用，因为在splay的时候会更新 root数组
rotate 不可以任意顺序，会有影响
/*
* @Author: zhl
* @Date: 2020-11-16 13:51:18
*/
#include<bits/stdc++.h>
#define mid (l+r>>1)
#define lo (o<<1)
#define ro (o<<1|1)
using namespace std;
const int N = 2e6 + 10, inf = 0x7fffffff;
struct node
int s[2], size, p, v;
void init(int _p, int _v)
p = _p; v = _v; size = 1;
tr[N];
int w[N], n, m, root[N], idx;
void push_up(int u)
tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
void rotate(int x)
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x; tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1]; tr[tr[x].s[k ^ 1]].p = y; //草这两行顺序不能换
tr[x].s[k ^ 1] = y; tr[y].p = x;
push_up(y), push_up(x);
void splay(int x, int k,int rt)
while (tr[x].p != k)
int y = tr[x].p, z = tr[y].p;
if (z != k)
if ((tr[z].s[0] == y) ^ (tr[y].s[0] == x)) rotate(x);
else rotate(y);
rotate(x);
if (!k)root[rt] = x;
void insert(int v, int rt)
int u = root[rt], p = 0;
while (u) p = u, u = tr[u].s[v > tr[u].v];
u = ++idx;
if (p)tr[p].s[v > tr[p].v] = u;
tr[u].init(p, v);
splay(u, 0, rt);
int get_rank(int v, int rt)
int u = root[rt], res = 0;
while (u)
if (v > tr[u].v) res += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
else u = tr[u].s[0];
return res;
void build(int o, int l, int r)
insert(-inf, o); insert(inf, o);
for (int i = l; i <= r; i++)
insert(w[i], o);
if (l == r)return;
build(lo, l, mid);
build(ro, mid + 1, r);
int query_rank(int o, int l, int r, int L, int R, int x)
if (L <= l and r <= R)return get_rank(x, o) - 1;
int ans = 0;
if (L <= mid)ans += query_rank(lo, l, mid, L, R, x);
if (R > mid) ans += query_rank(ro, mid + 1, r, L, R, x);
return ans;
void updt(int o, int l, int r, int pos, int v)
int u = root[o];
while (u)
if (tr[u].v == w[pos])break;
if (w[pos] > tr[u].v)u = tr[u].s[1];
if (w[pos] < tr[u].v) u = tr[u].s[0];
splay(u, 0, o);
int ls = tr[u].s[0], rs = tr[u].s[1];
while (tr[ls].s[1]) ls = tr[ls].s[1];
while (tr[rs].s[0]) rs = tr[rs].s[0];
splay(ls, 0, o); splay(rs, ls, o);
tr[rs].s[0] = 0;
push_up(rs); push_up(ls);
insert(v, o);
if (l == r)return; //不要忘记结束条件
if (pos <= mid)
updt(lo, l, mid, pos, v);
else
updt(ro, mid + 1, r, pos, v);
int get_pre(int x,int rt)
int u = root[rt], res = -inf;
while (u)
if (tr[u].v >= x) u = tr[u].s[0];
else res = tr[u].v, u = tr[u].s[1];
return res;
int get_suc(int x,int rt)
int u = root[rt], res = -inf;
while (u)
if (tr[u].v <= x) u = tr[u].s[1];
else res = tr[u].v, u = tr[u].s[0];
return res;
int query_pre(int o, int l, int r, int L, int R, int x)
if (L <= l and r <= R)return get_pre(x, o);
int ans = -inf;
if (L <= mid)ans = max(ans, query_pre(lo, l, mid, L, R, x));
if (R > mid) ans = max(ans, query_pre(ro, mid + 1, r, L, R, x));
return ans;
int query_suc(int o, int l, int r, int L, int R, int x)
if (L <= l and r <= R)return get_suc(x, o);
int ans = inf;
if (L <= mid)ans = min(ans, query_suc(lo, l, mid, L, R, x));
if (R > mid) ans = min(ans, query_suc(ro, mid + 1, r, L, R, x));
return ans;
int main()
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", w + i);
build(1, 1, n);
while (m--)
int op, a, b, k, pos;
scanf("%d", &op);
if (op == 1)
scanf("%d%d%d", &a, &b, &k);
printf("%d
", query_rank(1, 1, n, a, b, k) + 1);
else if (op == 2)
scanf("%d%d%d", &a, &b, &k);
int l = 0, r = 1e8;
while (l < r)
int m = l + r + 1 >> 1;
if (query_rank(1, 1, n, a, b, m) + 1 <= k)
l = m;
else
r = m - 1;
printf("%d
", r);
else if (op == 3)
scanf("%d%d", &pos, &k);
updt(1, 1, n, pos, k);
w[pos] = k;
else if (op == 4)
scanf("%d%d%d", &a, &b, &k);
printf("%d
", query_pre(1, 1, n, a, b, k));
else if (op == 5)
scanf("%d%d%d", &a, &b, &k);
printf("%d
", query_suc(1, 1, n, a, b, k));
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
uvalive-6709树套树(代码片段)
...法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情
hdu4819mosaic树套树(代码片段)
...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情
「题解」树套树tree(代码片段)
本文将同步发布于：洛谷博客；csdn；博客园；简书。题目题目描述给你一个\\(n\\)个点的小树（正常的树），给你一个\\(m\\)个点的大树，大树的节点是一棵小树，大树的边是跨越了两棵小树之间的边，\\(q\\)次询问，求树上距离... 查看详情
hdu6096树套树(代码片段)
思路：网上的题解有AC自动机的，有trie树的，还有（乱搞？）的 首先把输入的那n个串按照字典序排序，把n个串翻转以后再按照字典序排序这样我们发现，查的前缀在字典序排序后是一段区间，查的后缀翻转一下在翻转后的... 查看详情
「luogu3380」模板二逼平衡树（树套树）(代码片段)
「luogu3380」【模板】二逼平衡树（树套树）传送门我写的树套树——线段树套平衡树。线段树上的每一个节点都是一棵( extFHQTreap)，然后我们就可以根据平衡树的基本操作以及线段树上区间信息可合并的性质来实现了，具体细节... 查看详情
4889:[tjoi2017]不勤劳的图书管理员树套树(代码片段)
...惯例的题面(Bzoj没有，洛谷找的):动态加权逆序对，一眼树套树。256MB内存，5e4范围，不虚不虚。首先把交换改成两个插入和两个删除。考虑插入和删除的贡献，就是统计前面比这个值大的数的数值和，数量和，后面比这个值小的... 查看详情
97:cf983e倍增+树套树(代码片段)
$des$一棵$n$个点的树，树上有$m$条双向的公交线路，每条公交线路都在两个节点之间沿最短路径往返。$q$次询问从一个点要到达另一个点，在只坐公交的情况下，至少需要坐几辆公交车；或者判断无法只坐公交到达。$n,m,q<=2 ime... 查看详情
树套树(代码片段)
历时三天终于打过了树套树 激动激动激动写个博客纪念一下 二逼平衡树~//luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<stack>#include<queue>usingna... 查看详情
线段树树套树杭电ojluckandlove(代码片段)
博客主页:https://blog.csdn.net/qq_50285142欢迎点赞👍收藏✨关注❤留言📝如有错误，敬请指正🎈虽然生活很难，但我们也要一直走下去🎈题目链接思路：问题是要询问满足两个区间的最大缘分值，因为... 查看详情
二逼平衡树（树套树）(代码片段)
第一次写树套树，在一定帮助下学习，调码3h。用线段树套平衡树，对于区间内排名的查询可以解决了；//$O(log^2n)$对于查询区间排名为k的数，二分答案再判断；//$O(log^3n)$修改数值直接修改；//$O(log^2n)$前驱后继，线段树递归区间... 查看详情
二维线段树之树套树(代码片段)
1//poj1195二维线段树之树套树2//先确定横坐标所在的区间并记录该结点的编号p，然后再确定纵坐标所在的区间并记录该结点的编号cur，则tree[cur][p]为目标区间。3#include<cstdio>4#include<cstdlib>5#include<cstring>6#include<cmath&g... 查看详情
「模板」树套树
「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过，但我删除SBT点的时候没回收内存！写了就RE！先放上来吧，回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情
洛谷p3380模板二逼平衡树（树套树，树状数组，线段树）(代码片段)
洛谷题目传送门emm。。。题目名写了个平衡树，但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧。就像dynamicranking那样（蒟蒻的Sol,放一个link骗访问量233）所有的值（包括初始a数组，操作1、3、4、5的k）全部先... 查看详情
模板二逼平衡树（树套树）(代码片段)
...但是码量绝对是很大的一种方法居然控制在了6KB以内线段树套红黑树（逃这是一次前所未有的尝试因为线段树套平衡树求区间第(k)小复杂度是(mathrmO(log^3n))的所以速度比不上树状数组套线段树但是应该在线段树套平衡树的代码中... 查看详情
p3759[tjoi2017]不勤劳的图书管理员[树套树](代码片段)
树套树是什么啊我不知道/dk我只知道卡常数w//byIsaunoya#pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize("Ofast")#pragmaGCCoptimize("inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falig... 查看详情
[luogup3157][cqoi2011]动态逆序对(树套树)(代码片段)
...在外面再套上一颗树。这就很shit了。你问我资磁不资磁树套树，我是不资磁的，树套树是暴力数据结构，我能资磁吗？很不幸，昨天现实狠狠地打了我一脸：时间不够开新坑的，不切题又浑身难受，找了半天题，还是把这道题... 查看详情