前段时间在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