树套树 初步

树套树，顾名思义是将如 线段树、树状数组、平衡树 等树形数据结构结合起来，以实现更复杂的信息的维护

在线数据结构！！！

线段树/树状数组 套 动态开点线段树

通常用来处理二维信息

很常见的套路：数据结构题，有 $l$ 有 $r$ 还有时间戳，对其中一维扫描线，另两维用树套树维护

注意，它最适合处理的是 单点修改、矩形查询 问题，因为外层线段树懒标记是不好传的，但有的题也能

时空复杂度均为 $O(nlo{g}^2)$

具体应用

1]  三维偏序

按 $a_i$ 排序，另两维看作二维数点的话就是 单点加、矩形查 操作

静态线段树 套 值域线段树 版

#include<bits/stdc++.h>
using namespace std ;

typedef long long LL ;
const int N = 1e5+100 , M = 2e5+100 ; 

int n , K , f[N] ;
struct nn
{
	int a , b , c ;
}p[N] ;
bool cmp( nn x , nn y )
{
	return x.a < y.a ;
}
struct Segtree
{
	int l , r , rt ;
}t[8*N] ;
struct Segtree1
{
	int ls , rs , sum ;
}tre[240*N] ;// 内层动态开点线段树维护 C , log^2 个节点 
int tot ;
inline int tre_build() { return ++tot ; }
void build( int p , int l , int r )
{
	t[p].l = l , t[p].r = r , t[p].rt = tre_build() ;
	if( l == r ) {
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	build( p<<1 , l , mid ) ; build( p<<1|1 , mid+1 , r ) ;
}
void Insert( int p , int l , int r , int x )
{
	if( l == r ) {
		tre[p].sum ++ ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	if( x <= mid ) {
		if( !tre[p].ls ) tre[p].ls = tre_build() ;
		Insert( tre[p].ls , l , mid , x ) ;
	}
	else {
		if( !tre[p].rs ) tre[p].rs = tre_build() ;
		Insert( tre[p].rs , mid+1 , r , x ) ; 
	}
	tre[p].sum = tre[tre[p].ls].sum + tre[tre[p].rs].sum ;
}
void modify( int p , int B , int C )
{
	Insert( t[p].rt , 1 , K , C ) ; // 从上往下修改 
	if( t[p].l == t[p].r ) {
		return ;
	}
	int mid = ( t[p].l + t[p].r ) >> 1 ;
	if( B <= mid ) modify( p<<1 , B , C ) ;
	else modify( p<<1|1 , B , C ) ;
	// 无法 push up ，不能维护诸如 Max 等信息 
}
int tre_query( int p , int l , int r , int C )
{
	if( !p ) return 0 ;
	if( r <= C ) {
		return tre[p].sum ;
	}
	int mid = ( l + r ) >> 1 ;
	if( C <= mid ) return tre_query( tre[p].ls, l , mid , C ) ;
	return tre[tre[p].ls].sum + tre_query( tre[p].rs , mid+1 , r , C ) ;
}
int query( int p , int B , int C ) // 查 [1,B] 中的线段树 
{
	if( t[p].r <= B ) {
		return tre_query( t[p].rt , 1 , K , C ) ;
	}
	int mid = ( t[p].l + t[p].r ) >> 1 , res = 0 ;
	res += query( p<<1 , B , C ) ;
	if( mid < B ) res += query( p<<1|1 , B , C ) ;
	return res ;
}

int main()
{
	scanf("%d%d" , &n , &K ) ;
	for(int i = 1 ; i <= n ; i ++ ) {
		scanf("%d%d%d" , &p[i].a , &p[i].b , &p[i].c ) ;
	}
	sort( p+1 , p+n+1 , cmp ) ;
	build( 1 , 1 , K ) ; // 外层静态线段树维护 b 
	for(int i = 1 , j = 1 ; i <= n ; i ++ ) {
		while( j <= n && p[j].a == p[i].a ) {
			modify( 1 , p[j].b , p[j].c ) ;
			j ++ ;
		}
		int ans = query( 1 , p[i].b , p[i].c ) - 1 ;
		f[ans] ++ ;
	}
	for(int i = 0 ; i < n ; i ++ ) {
		printf("%d\n" , f[i] ) ; 
	}
	return 0 ;
}

我们会发现，外层线段树 无法进行 push up 操作！！！（也有可能是我还不会）

原因在于 没法在可观的复杂度内合并 ls 与 rs 对应的线段树

因此我们只能采取递归时从上往下更新的方式

这样的后果是能够维护的信息大大受限制 （比如 Max 这样依赖于儿子节点的信息）

树状数组 套 值域线段树 版

struct BIT
{
	int rt[M] ;
	struct Segtree
	{
		int ls , rs , sum ;
	}t[16*16*M] ;
	int tot ;
	inline int build() { return ++tot ; }
	inline int lowbit( int x ) { return x&-x ; }
	void Insert( int p , int l , int r , int C )
	{
		if( l == r ) {
			t[p].sum ++ ;
			return ;
		}
		int mid = ( l + r ) >> 1 ;
		if( C <= mid ) {
			if( !t[p].ls ) t[p].ls = build() ;
			Insert( t[p].ls , l , mid , C ) ;
		}  
		else {
			if( !t[p].rs ) t[p].rs = build() ;
			Insert( t[p].rs , mid+1 , r , C ) ;
		}
		t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum ;
	 }
	void add( int p , int C )
	{
		for( ; p <= K ; p += lowbit(p) ) {
			Insert( rt[p] , 1 , K , C ) ;
		}
	}
	int query( int p , int l , int r , int C ) // <= C 
	{
		if( !p ) return 0 ;
		if( r <= C ) {
			return t[p].sum ;
		}
		int mid = ( l + r ) >> 1 , res = 0 ;
		res += query( t[p].ls , l , mid , C ) ;
		if( C > mid ) res += query( t[p].rs , mid+1 , r , C ) ;
		return res ;
	}
	int ask( int p , int C )
	{
		int res = 0 ;
		for( ; p ; p -= lowbit(p) ) {
			res += query( rt[p] , 1 , K , C ) ;
		}
		return res ;
	}
} T ;

树状数组本身就能将原序列任意一个区间 划分成 $log$ 个

原来维护值的 $t$ 数组改为维护线段树根节点的 $rt$ 数组，查询\修改时在 $t[rt]$ 中做

码量、常数 显著减小

2] 带修区间第 $K$ 小 传送门

树状数组 套 主席树

静态时我们主席树维护的时 是一段前缀信息，但这样带修根本做不了

考虑前缀信息用树状数组处理，我们就得到了 单修主席树

本题要求第 $K$ 大，这种信息显然不具有可加减性，那么一个转化是找到某个数 $x$ 使得小于它的元素恰有 $K$ 个，这样对于元素个数的信息就能加减啦

直接二分是 $O(nlo{g}^3)$ 的，我们照搬线段树二分的思路，对于树状数组上的 $log$ 个区间让它们一起往儿子走，每层把 $log$ 个节点拿出来就行

// 单修主席树 
struct BIT
{
	int rt[N] ;
	inline int lowbit( int x ) { return x&-x ; }
	struct Segtree
	{
		int ls , rs , sum ;
	}t[N*18*18] ;
	int tot ;
	inline int build() { return ++tot ; }
	void Insert( int p , int l , int r , int x , int f )
	{
		if( l == r ) {
			t[p].sum += f ;
			return ;
		} 
		int mid = ( l + r ) >> 1 ;
		if( x <= mid ) {
			if( !t[p].ls ) t[p].ls = build() ;
			Insert( t[p].ls , l , mid , x , f ) ;
		} 
		else {
			if( !t[p].rs ) t[p].rs = build() ;
			Insert( t[p].rs , mid+1 , r , x , f ) ;
		}
		t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum ;
	}
	void add( int p , int x , int f ) {
		for( ; p <= n ; p += lowbit(p) ) {
			Insert( rt[p] , 0 , INF , x , f ) ;
		}
	}
	int t1[32] , t2[32] , cnt1 , cnt2 , tp[32] , len ; // 同一层 log 个区间的，一起往下走 
	int query( int l , int r , int K )
	{
		if( l == r ) {
			return l ;
		} 
		int sum = 0 , mid = (l+r) >> 1 ;
		for(int i = 1 ; i <= cnt1 ; i ++ ) sum -= t[t[t1[i]].ls].sum ;
		for(int i = 1 ; i <= cnt2 ; i ++ ) sum += t[t[t2[i]].ls].sum ;
		if( sum >= K ) {
			len = 0 ;
			for(int i = 1 ; i <= cnt1 ; i ++ ) {
				if( t[t1[i]].ls ) tp[++len] = t[t1[i]].ls ;
			}
			for(int i = 1 ; i <= len ; i ++ ) t1[i] = tp[i] ;
			cnt1 = len ;
			len = 0 ;
			for(int i = 1 ; i <= cnt2 ; i ++ ) {
				if( t[t2[i]].ls ) tp[++len] = t[t2[i]].ls ;
			}
			for(int i = 1 ; i <= len ; i ++ ) t2[i] = tp[i] ;
			cnt2 = len ;
			return query( l , mid , K ) ;
		}
		K -= sum ;
		len = 0 ;
		for(int i = 1 ; i <= cnt1 ; i ++ ) {
			if( t[t1[i]].rs ) tp[++len] = t[t1[i]].rs ;
		}
		for(int i = 1 ; i <= len ; i ++ ) t1[i] = tp[i] ;
		cnt1 = len ;
		len = 0 ;
		for(int i = 1 ; i <= cnt2 ; i ++ ) {
			if( t[t2[i]].rs ) tp[++len] = t[t2[i]].rs ;
		}
		for(int i = 1 ; i <= len ; i ++ ) t2[i] = tp[i] ;
		cnt2 = len ;
		return query( mid+1 , r , K ) ;
	}
	int ask( int l , int r , int k ) {
		cnt1 = cnt2 = 0 ;
		l -- ;
		for( ; l ; l -= lowbit(l) ) t1[++cnt1] = rt[l] ;
		for( ; r ; r -= lowbit(r) ) t2[++cnt2] = rt[r] ;
		return query( 0 , INF , k ) ;
	}
	void pre_work()
	{
		for(int i = 1 ; i <= n ; i ++ ) {
			rt[i] = build() ;
		}
		for(int i = 1 ; i <= n ; i ++ ) add( i , a[i] , 1 ) ;
	}
} T ;

不知道为什么常数这么大 呜呜呜