前段时间在CCPC-Wannafly-Wintercamp做到了一道矩阵求最值的题目，std大概是用二维线段树来完成的。之前一直纠结树套树的空间复杂度问题，一直没敢尝试，听说当时有队伍用st表离线卡过去，但是我补题的时候卡了一晚上也没成功，队友套了个树套树的板子，总算是成功过掉了。
今天来把这块漏补掉。

线段树套线段树

所谓树套树，就是二维的树，对于树上的每一个节点，又是一棵树。
这里以线段树套线段树处理三维偏序问题为例，陌上花开
题目大意：)个点，对于每一个)找出有几个)满足)
做法：对于二维偏序，我们可以离线后对)排序，用线段树或树状数组对)求解，同理，三维偏序可以离线后对)排序然后对建二维线段树处理

二维线段树

一棵二维的线段树，对于外围的线段树，维护)轴的信息，每个结点代表的线段树维护轴的信息。所以实际上是对一张二维的矩阵，按行来用线段树维护。原本普通的线段树维护的是一个元素一个元素的合并维护，现在是一行一行的合并维护。
考虑一下这么做的复杂度：之前一直担心的是对于每个节点建一棵线段树，空间会炸，但是发现了实际上二维的线段树是可以动态开点进行维护的，也就是说对于没有信息的点，我们大可不必专门开内存。对于)个信息，每个信息的范围是),所以每个点只需要)个点的信息，满打满算只有的空间复杂度，所以是可以接受的。

对于时间复杂度，每一维需要)的复杂度去维护，所以总复杂度是级别的。

代码实现

声明内存

int nodez[maxn * 90], tot, ls[maxn * 90], rs[maxn * 90];//对于z开一堆线段树，用tot动态分配；按理说*30够够的了，不知道为啥最后一个点一直re，最后开到90终于过了
int rt[maxn << 2];//一维的线段树可以直接按四倍开，不需要动态分配，因为方便2333

更新

暂时没有实现区间更新，只写了单点更新的操作，等之后再补充

void updatez(int root, int l, int r, int z, int v)//对于z轴信息的更新
{
    if (l == r)//递归到一个点时，退出递归
    {
        nodez[root] += v;
        return;
    }
    int mid = l + r >> 1;
    if (z <= mid)//递归地更新左子树
    {
        if(!ls[root])//如果左子树不存在，也就是之前左子树没有储存过信息，没有分配
            ls[root] = ++tot;//用tot分配一个内存
        updatez(ls[root], l, mid, z, v);
    }
    else//同理更新右子树
    {
        if(!rs[root])
            rs[root] = ++tot;
        updatez(rs[root], mid + 1, r, z, v);
    }
    pushup(root);//合并左右子树地信息，向上push
}

void updatey(int root, int l, int r,int y,int z, int v)//对y轴进行更新
{
    if(!rt[root])//如果当前节点不存在需要新开一个节点
        rt[root] = ++tot;
    // assert(rt[root] >= (maxn << 7));
    updatez(rt[root], 1, k, z, v);//对于每一个包含z的区间都要进行相应的修改，因为我不知道二维线段树该如何打标记
    pushup(rt[root]);
    if (l == r)//递归终点
    {
        return;
    }
    int mid = l + r >> 1;
    if (y <= mid)//递归更新左子树
    {
        updatey(lson, y, z, v);
    }
    else//更新右子树
    {
        updatey(rson, y, z, v);
    }
}//可以看到其实y轴这一维是没有实际上的树的，储存的其实是树的根，这是我对树套树的理解，如果有更好的写法，之后再更新

查询

int queryz(int root, int l, int r, int lz, int rz)//对于z轴只需要按正常线段树查询的步骤查询即可
{
    if (l == lz && r == rz)
    {
        return nodez[root];
    }
    int mid = l + r >> 1;
    if (rz <= mid)
        return queryz(ls[root], l, mid, lz, rz);
    else if (lz > mid)
        return queryz(rs[root], mid + 1, r, lz, rz);
    else
    {
        return queryz(ls[root], l, mid, lz, mid) + queryz(rs[root], mid + 1, r, mid + 1, rz);
    }
}

int queryy(int root, int l, int r, int ly, int ry, int lz, int rz)//对y轴的查询
{

    if (l == ly && r == ry)
    {
        return queryz(rt[root], 1, k, lz, rz);//但查询区间和现在的区间重合时，询问z轴
        //因为节点上实际储存的是一棵线段树，所以z轴的查询区间实际上又是[1,k]
    }
    int mid = l + r >> 1;
    if (ry <= mid)//递归地查询并合并答案即可
        return queryy(lson, ly, ry, lz, rz);
    else if (ly > mid)
        return queryy(rson, ly, ry, lz, rz);
    else
    {
        return queryy(lson, ly, mid, lz, rz) + queryy(rson, mid + 1, ry, lz, rz);
    }
}

以上是本人对(权值)线段树套(权值)线段树的理解，实际上是按照自己的想法瞎写的，不知道各位神神犇有没有更好的做法，之后可能会更新更优的做法
实际上线段树套线段树是无法过上述题目的，卡常卡了一晚上，最后把第一维替换成树状数组终于成功ac
这里再贴一下第一维是树状数组的做法

//只有y轴被改成了树状数组，z轴没变
void updatey(int y,int z, int v)
{
    for (; y <= k; y += lowbit(y))
    {
        if(!rt[y])
            rt[y] = ++tot;
        updatez(rt[y], 1, k, z, v);
        pushup(rt[y]);
    }
}

int queryy(int y, int lz, int rz)
{
    int res = 0;
    for (; y > 0; y -= lowbit(y))
    {
        if(!rt[y])//反正这个点是空的，索性不用查询
            continue;
        res += queryz(rt[y], 1, k, lz, rz);
    }
    return res;
}

以上，欢迎各位dalao提意见

or2