总述：
将平衡树的操作搬到区间上，如果没有修改操作，可以用主席树做做。如果有修改，主席树就难办了。这时可用线段树套平衡树。
平时我们用几个变量维护线段树节点信息。操作复杂时，几个变量不能完成任务，可用更强大的平衡树维护线段树节点信息（树套树的本质）。题目能用线段树做，那么题目问题定可以分解或转化成小问题（大区间可由若干小区间合并得到答案）。
套的平衡树依题而定，会影响常数。树套树常数很大（尤其在套splay的情况下）。
各操作实现参考大佬博客：浅谈树套树(线段树套平衡树)&学习笔记
个人AC代码（线段树套splay400行版）
1 #include<iostream> 2 #include<cstdio> 3 4 #define qiuls (t<<1) 5 #define qiurs ((t<<1)|1) 6 #define qiumid (l+r>>1) 7 8 using namespace std; 9 10 const int N=5e4+5,FINF=-2147483647,INF=2147483647; 11 12 int tre[N<<2],n,m,cnt,upp[N*56],ans; 13 14 long long ai[N]; 15 16 struct node{ 17 int f,so[2],nu,w,siz; 18 }s[N*56]; 19 20 inline long long read()//ll N 21 { 22 long long x=0; 23 bool f=0; 24 char ch=getchar(); 25 while(!isdigit(ch)) 26 f|=ch=='-',ch=getchar(); 27 while(isdigit(ch)) 28 x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 29 return f?-x:x; 30 } 31 32 inline int newnode(long long v) 33 { 34 s[++cnt].nu=v; 35 s[cnt].siz=s[cnt].w=1; 36 return cnt; 37 } 38 39 inline void rotate(int t) 40 { 41 int u=s[t].f; 42 if(!u) 43 return; 44 int ff=s[u].f; 45 if(upp[u]) 46 { 47 upp[t]=upp[u]; 48 tre[upp[t]]=t; 49 upp[u]=0; 50 } 51 if(ff) 52 s[ff].so[s[ff].so[1]==u]=t; 53 int st=s[u].so[1]==t; 54 int v=s[t].so[!st]; 55 s[t].f=ff; 56 s[u].f=t; 57 s[u].so[st]=v; 58 if(v) 59 s[v].f=u; 60 s[t].so[!st]=u; 61 s[u].siz=s[s[u].so[0]].siz+s[s[u].so[1]].siz+s[u].w; 62 s[t].siz=s[s[t].so[0]].siz+s[s[t].so[1]].siz+s[t].w; 63 } 64 65 void splay(int t,int ff) 66 { 67 int u,v; 68 while(s[t].f!=ff) 69 { 70 u=s[t].f; 71 if(s[u].f==ff) 72 { 73 rotate(t); 74 return; 75 } 76 else 77 v=s[u].f; 78 if((s[u].so[1]==t)==(s[v].so[1]==u)) 79 rotate(u),rotate(t); 80 else 81 rotate(t),rotate(t); 82 } 83 } 84 85 void sinsert(int t,int v) 86 { 87 s[t].siz++; 88 if(v==s[t].nu) 89 { 90 s[t].w++; 91 splay(t,0); 92 return; 93 } 94 if(v<s[t].nu) 95 { 96 if(s[t].so[0]) 97 sinsert(s[t].so[0],v); 98 else 99 { 100 s[t].so[0]=newnode(v); 101 s[cnt].f=t; 102 splay(cnt,0); 103 } 104 } 105 else 106 { 107 if(s[t].so[1]) 108 sinsert(s[t].so[1],v); 109 else 110 { 111 s[t].so[1]=newnode(v); 112 s[cnt].f=t; 113 splay(cnt,0); 114 } 115 } 116 } 117 118 void build(int t,int l,int r)//有虚点 119 { 120 tre[t]=++cnt; 121 upp[cnt]=t; 122 s[cnt].nu=FINF; 123 s[cnt].siz=s[cnt].w=1; 124 sinsert(cnt,INF); 125 for(int i=l;i<=r;++i) 126 sinsert(tre[t],ai[i]); 127 if(l==r) 128 return; 129 build(qiuls,l,qiumid); 130 build(qiurs,qiumid+1,r); 131 } 132 133 int sfinrank(int t,long long k) 134 { 135 if(!t) 136 return 0; 137 if(k==s[t].nu) 138 { 139 int ret=s[s[t].so[0]].siz; 140 splay(t,0); 141 return ret; 142 } 143 if(k<s[t].nu) 144 { 145 if(s[t].so[0]) 146 return sfinrank(s[t].so[0],k); 147 else 148 { 149 splay(t,0); 150 return 0; 151 } 152 } 153 else 154 { 155 if(s[t].so[1]) 156 return s[s[t].so[0]].siz+s[t].w+sfinrank(s[t].so[1],k); 157 else 158 { 159 int ret=s[s[t].so[0]].siz+s[t].w; 160 splay(t,0); 161 return ret; 162 } 163 } 164 } 165 166 void finrank(int t,int l,int r,int ll,int rr,long long k)//多少数小于k 167 { 168 if(ll<=l&&r<=rr) 169 { 170 ans+=sfinrank(tre[t],k)-1; 171 return; 172 } 173 int mid=qiumid; 174 if(ll<=mid) 175 { 176 if(rr>mid) 177 finrank(qiuls,l,mid,ll,rr,k),finrank(qiurs,mid+1,r,ll,rr,k); 178 else 179 finrank(qiuls,l,mid,ll,rr,k); 180 } 181 else 182 finrank(qiurs,mid+1,r,ll,rr,k); 183 } 184 185 void sdel(int t,long long k) 186 { 187 s[t].siz--; 188 if(!t) 189 { 190 cout<<"****"; 191 return; 192 } 193 if(k==s[t].nu) 194 { 195 if(s[t].w>1) 196 { 197 s[t].w--; 198 splay(t,0); 199 return; 200 } 201 if(s[t].so[0]&&s[t].so[1]) 202 { 203 int u=s[t].so[0]; 204 while(s[u].so[1]) 205 u=s[u].so[1]; 206 if(upp[t]) 207 { 208 upp[u]=upp[t]; 209 tre[upp[u]]=u; 210 } 211 s[s[t].f].so[s[s[t].f].so[1]==t]=u; 212 s[s[t].so[1]].f=u; 213 if(u==s[t].so[0]) 214 { 215 s[u].f=s[t].f;s[u].siz=s[t].siz; 216 s[u].so[1]=s[t].so[1]; 217 splay(u,0); 218 } 219 else 220 { 221 int v=s[t].so[0]; 222 while(v!=u) 223 { 224 s[v].siz--; 225 v=s[v].so[1]; 226 } 227 if(s[u].so[0]) 228 s[s[u].so[0]].f=t; 229 s[s[t].so[0]].f=u; 230 s[s[u].f].so[1]=t; 231 swap(s[u].f,s[t].f); 232 swap(s[u].so,s[t].so); 233 swap(s[u].siz,s[t].siz); 234 sdel(t,k); 235 } 236 } 237 else 238 { 239 int u=s[t].so[0]+s[t].so[1]; 240 s[s[t].f].so[s[s[t].f].so[1]==t]=u; 241 if(u) 242 s[u].f=s[t].f; 243 splay(s[t].f,0); 244 } 245 } 246 else 247 { 248 if(k<s[t].nu) 249 sdel(s[t].so[0],k); 250 else 251 sdel(s[t].so[1],k); 252 } 253 } 254 255 void modify(int t,int l,int r,int ll,long long k) 256 { 257 //注意splay变空的情况 258 //更新，因为有虚点，所以不会变空 259 sdel(tre[t],ai[ll]); 260 sinsert(tre[t],k); 261 if(l==r) 262 return; 263 int mid=qiumid; 264 if(ll<=mid) 265 modify(qiuls,l,mid,ll,k); 266 else 267 modify(qiurs,mid+1,r,ll,k); 268 } 269 270 void sfinpre(int t,long long k) 271 { 272 if(!t) 273 return; 274 if(s[t].nu<k) 275 { 276 ans=max(ans,s[t].nu); 277 if(s[t].so[1]) 278 sfinpre(s[t].so[1],k); 279 else 280 splay(t,0); 281 } 282 else 283 if(s[t].so[0]) 284 sfinpre(s[t].so[0],k); 285 else 286 splay(t,0); 287 } 288 289 void sfinnxt(int t,long long k) 290 { 291 if(!t) 292 return; 293 if(s[t].nu>k) 294 { 295 ans=min(ans,s[t].nu); 296 if(s[t].so[0]) 297 sfinnxt(s[t].so[0],k); 298 else 299 splay(t,0); 300 } 301 else 302 if(s[t].so[1]) 303 sfinnxt(s[t].so[1],k); 304 else 305 splay(t,0); 306 } 307 308 void finpre(int t,int l,int r,int ll,int rr,long long k) 309 { 310 if(ll<=l&&r<=rr) 311 { 312 sfinpre(tre[t],k); 313 return; 314 } 315 int mid=qiumid; 316 if(ll<=qiumid) 317 { 318 if(rr>qiumid) 319 finpre(qiuls,l,mid,ll,rr,k),finpre(qiurs,mid+1,r,ll,rr,k); 320 else 321 finpre(qiuls,l,mid,ll,rr,k); 322 } 323 else 324 finpre(qiurs,mid+1,r,ll,rr,k); 325 } 326 327 void finnxt(int t,int l,int r,int ll,int rr,long long k) 328 { 329 if(ll<=l&&r<=rr) 330 { 331 sfinnxt(tre[t],k); 332 return; 333 } 334 int mid=qiumid; 335 if(ll<=qiumid) 336 { 337 if(rr>qiumid) 338 finnxt(qiuls,l,mid,ll,rr,k),finnxt(qiurs,mid+1,r,ll,rr,k); 339 else 340 finnxt(qiuls,l,mid,ll,rr,k); 341 } 342 else 343 finnxt(qiurs,mid+1,r,ll,rr,k); 344 } 345 346 int main() 347 { 348 n=read(),m=read(); 349 for(int i=1;i<=n;++i) 350 ai[i]=read(); 351 build(1,1,n); 352 int opt,l,r; 353 long long k; 354 int ll,rr,mid; 355 for(int i=1;i<=m;++i) 356 { 357 opt=read(); 358 switch(opt) 359 { 360 case 1: 361 l=read(),r=read(),k=read(); 362 ans=0; 363 finrank(1,1,n,l,r,k); 364 printf("%d ",ans+1); 365 break; 366 case 2: 367 l=read(),r=read(),k=read(); 368 ll=0,rr=1e8; 369 while(ll<rr) 370 { 371 mid=(ll+rr)>>1; 372 ans=0; 373 finrank(1,1,n,l,r,mid); 374 if(ans<k) 375 ll=mid+1; 376 else 377 rr=mid; 378 } 379 printf("%d ",ll-1); 380 break; 381 case 3: 382 l=read(),k=read(); 383 modify(1,1,n,l,k); 384 ai[l]=k; 385 break; 386 case 4: 387 l=read(),r=read(),k=read(); 388 if(k<=0) 389 { 390 printf("%d ",FINF); 391 break; 392 } 393 ans=-INF; 394 finpre(1,1,n,l,r,k); 395 printf("%d ",ans); 396 break; 397 case 5: 398 l=read(),r=read(),k=read(); 399 if(k>=1e8) 400 { 401 printf("%d ",INF); 402 break; 403 } 404 ans=INF; 405 finnxt(1,1,n,l,r,k); 406 printf("%d ",ans); 407 break; 408 } 409 } 410 return 0; 411 }
代码中给每个线段树的节点上的splay都多加了两个虚点-INF和INF 一能防止modify的删除节点时使splay变空的情况，二能防止没有前驱/后缀的情况。后来想一想，发现实际上对于情况1，先加后删就行；情况二：因为用的全局变量ans取遇见的最优值，只要ans初值设好，也不怕没前驱/后继。总之，虚点不用加了，加了还得考虑对sfinrank的影响（减一），画蛇添足。
几个注意点：
1、内存：线段树为4N*int，所有splay的总内存：
（2（虚点内存。不用虚点 可不加2） + (ceil(logn)+1)(线段树层数））*N+M* (ceil(logn)+1) *node （node为splay的节点结构体，存一个节点的全部信息）
不算虚点的话，splay的总内存为： (ceil(logn)+1)（N+M）*node
2、时间：上限复杂度：O(n log^3 n) 查排名为k的数单次操作复杂度为log^3 n
（听说用树状数组套主席树可以压到log^2 n ?）
3、平衡树中点的位置变动时，要注意维护：该点及其周围有联系的所有点的所有信息。别忘了该点被线段树上的点直接指向的情况。
4、用到splay的话，注意每次进入splay操作后都要进行一次'splay操作'，否则能被出题人造特殊数据卡；要在返回的答案（例如s[s[t].so[0]].siz+s[t].w等）记录下之后再splay操作，因为splay操作会改变splay的结构，即splay操作后，s[s[t].so[0]].siz+s[t].w很可能会变。
5、树套树代码量极大、调试难度高，不推荐解题时首选该方法。（众所周知树套树的题都能不用树套树做 ~逃）
常常被分块取代。可离线的话会被其他优秀算法（例如整体二分、cdq分治 （可惜现在都不会 捂脸）））各种暴打。
扩展应用：
1、区间修改：标记永久化