猫(娘)树

· · 算法·理论

猫树是一种不支持修改、只支持快速查询的数据结构,常用于处理询问复杂度较大的静态问题。

猫树

猫树和线段树的结构相同,因此可以直接借用线段树的结构图。

假设要查询区间 [l,r],先找到 [l,l] 和 [r,r] 这两个节点的 LCA [L,R]。此时 [L,R] 一定是第一个包含 [l,r] 的节点,并且 [l,r] 一定跨过 [L,R] 的中点。

例如查询 [3,7],就找 [3,3] 和 [7,7] 的 LCA,也就是 [1,7]。

找到 LCA 之后该做什么?可以在每个节点维护一个 [L,mid] 的后缀和数组 S,其中 S[x] 表示查询 [x,mid] 的答案;再维护一个 (mid,R] 的前缀和数组 B,其中 B[x] 表示查询 [mid+1,x] 的答案。于是查询 [l,r] 时,只需在对应的 LCA [L,R] 上计算 merge(S[l],B[r])。

因为需要求后缀和与前缀和,设一次合并的复杂度为 O(M),则建树复杂度为 T(n)=O(Mn)+2T\left(\frac{n}{2}\right)=O(Mn\log n)。单次查询复杂度为 O(M)。

但问题在于还需要求 LCA。真的要使用 Tarjan 或 ST 表吗?那样空间可能会比较吃紧。

因此可以把原序列补全到 2 的幂,这样树就变成一棵满二叉树。例如:

对节点标号:

稍加观察可以发现,每个位置 i 的编号刚好是 i+n-1。

如果两个编号的 LCA 刚好是它们的父亲,那么这两个编号除以 2 下取整后相同,且结果刚好是它们的 LCA 编号。

同理,如果是第 k 祖先,那么除以 2^k 下取整后也相同,并且结果就是 LCA 编号。于是只需要看这两个编号的低位有多少位不同;低几位不同,就除以 2 的多少次幂并下取整,把不同的低位去掉,剩下的就是 LCA 编号。

每一位是否相同,刚好可以用异或判断。众所周知,异或运算“相同为 0、不同为 1”,所以两数异或后有多少个二进制位,就需要除以 2 的多少次幂。一个数有多少位,显然为 \lfloor\log_2 x\rfloor+1。

因此两个编号的 LCA 为 \operatorname{lca}(x,y)=\left\lfloor\frac{x}{2^{\lfloor\log_2(x\oplus y)\rfloor+1}}\right\rfloor。查询时给出的是位置,需要先变成编号,所以 \operatorname{lca}(l,r)=\left\lfloor\frac{l+n-1}{2^{\lfloor\log_2((l+n-1)\oplus(r+n-1))\rfloor+1}}\right\rfloor。

这时又会发现:如果每个节点都开一个 vector,由于空间限制,下标都要整体减去一个 L,这会很麻烦,因为还需要记录每个节点编号对应的 L。

但每一层的数组互不相交,并起来刚好等于全集,所以不如直接按层记录所有节点的前缀和、后缀和拼接后的结果。这样既不需要偏移下标,还能减少 vector 带来的常数。

代码如下:

int s[logn][maxn], a[maxn], lg[maxn], n;
void build(int l, int r, int dep) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    s[dep][mid] = a[mid];
    for (int i = mid - 1; i >= l; i--) s[dep][i] = merge(a[i], s[dep][i + 1]);
    s[dep][mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++) s[dep][i] = merge(s[dep][i - 1], a[i]);
    build(l, mid, dep + 1), build(mid + 1, r, dep + 1);
}
int qry(int l, int r) {
    int p = lg[(l + n - 1) >> (lg[(l + n - 1) ^ (r + n - 1)] + 1)] + 1;
    return merge(s[p][l], s[p][r]);
}

猫树分治

正式考试中一般不会直接考猫树,通常考查的是猫树分治这一思想,虽然两者差别并不大。

所谓猫树分治,就是先将所有询问离线下来,在询问上分治,然后借用猫树的思想求解每个询问。

具体而言,每次递归时记录一个数组区间 [l,r] 和查询区间 [ql,qr]。

在查询区间中,把所有完全位于 mid 左侧的询问递归到 [l,mid],把所有完全位于 mid 右侧的询问递归到 [mid+1,r]。

对于所有跨过 mid 的询问,使用猫树的方法,算出当前区间 [l,mid] 的后缀和与 [mid+1,r] 的前缀和,然后直接用 merge(S[ql],B[qr]) 求得答案。

代码如下:

void solve(int l, int r, int ql, int qr) {
    if (l == r) {
        for (int i = ql; i <= qr; i++) ans[q[i].id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    s[mid] = a[mid];
    for (int i = mid - 1; i >= l; i--) s[i] = merge(a[i], s[i + 1]);
    b[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++) b[i] = merge(b[i - 1], a[i]);
    for (int i = ql; i <= qr; i++) tmp[i] = q[i];
    int cntl = ql, cntr = qr;
    for (int i = ql; i <= qr; i++) {
        if (tmp[i].r <= mid) q[cntl++] = tmp[i];
        else if (tmp[i].l > mid) q[cntr--] = tmp[i];
        else ans[tmp[i].id] = merge(s[tmp[i].l], b[tmp[i].r]);
    }
    solve(l, mid, ql, cntl - 1);
    solve(mid + 1, r, cntr + 1, qr);
}

猫树是什么复杂度,猫树分治就是什么复杂度。因此不少题目的猫树分治做法都可以转化为猫树,并且可以由离线变为在线。

为书写方便,下面例题代码均采用猫树分治做法,因为题目没有强制在线;想看猫树写法的读者可以自行尝试,从猫树分治转化到猫树理应是简单的。

例题

P11265 【模板】静态区间半群查询

题意:给定若干 2\times 2 矩阵,查询区间 (\min,+) 矩阵积。

模板题。

代码如下:

struct mat {
    int a[2][2];
    mat() { memset(a, 0x3f, sizeof(a)); }
    mat operator * (const mat &oth) const {
        mat res;
        for (int i = 0; i < 2; i++)
            for (int k = 0; k < 2; k++)
                for (int j = 0; j < 2; j++)
                    res.a[i][j] = min(res.a[i][j], a[i][k] + oth.a[k][j]);
        return res;
    }
    int operator ^ (const mat &oth) const {
        int res = 0;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                res += a[i][j] ^ oth.a[i][j];
        return res;
    }
} kv, a[maxn], s[maxn], b[maxn];
int ans[maxn];
struct node {
    int l, r, id;
} q[maxn], tmp[maxn];
void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return;
    if (l == r) {
        for (int i = ql; i <= qr; i++) ans[q[i].id] = a[l] ^ kv;
        return;
    }
    int mid = (l + r) >> 1;
    s[mid] = a[mid];
    for (int i = mid - 1; i >= l; i--) s[i] = a[i] * s[i + 1];
    b[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++) b[i] = b[i - 1] * a[i];
    for (int i = ql; i <= qr; i++) tmp[i] = q[i];
    int cntl = ql, cntr = qr;
    for (int i = ql; i <= qr; i++) {
        if (tmp[i].r <= mid) q[cntl++] = tmp[i];
        else if (tmp[i].l > mid) q[cntr--] = tmp[i];
        else ans[tmp[i].id] = s[tmp[i].l] * b[tmp[i].r] ^ kv;
    }
    solve(l, mid, ql, cntl - 1);
    solve(mid + 1, r, cntr + 1, qr);
}

P6240 好吃的题目

题意:给定 n 个物品的重量和价值,q 次查询区间限重 t 的最大价值,1\le n\le 40000,1\le q\le 200000,1\le t\le 200。

注意到背包是 O(tn) 的,但合并两个背包是 O(t^2) 的,这样复杂度是 O(tn\log n+qt^2),似乎不可接受。

但实际上并不需要真正合并,只需要计算

\max_{0\le i\le t}\left(S[l][i]+B[r][t-i]\right)

即可,复杂度降到 O(tn\log n+qt)。

另外,空间只有 125 MB,不要 #define int long long(

代码如下:

int w[maxn], v[maxn], b[maxn][250], s[maxn][250], ans[maxm];
struct node {
    int l, r, t, id;
} q[maxm], tmp[maxm];
void solve(int l, int r, int ql, int qr) {
    if (l == r) {
        for (int i = ql; i <= qr; i++) ans[q[i].id] = (w[l] <= q[i].t ? v[l] : 0);
        return;
    }
    int mid = (l + r) >> 1;
    for (int i = 0; i < w[mid]; i++) s[mid][i] = 0;
    for (int i = w[mid]; i <= 200; i++) s[mid][i] = v[mid];
    for (int i = mid - 1; i >= l; i--) {
        for (int j = 0; j < min(w[i], 201); j++) s[i][j] = s[i + 1][j];
        for (int j = w[i]; j <= 200; j++) s[i][j] = max(s[i + 1][j], s[i + 1][j - w[i]] + v[i]);
    }
    for (int i = 0; i < w[mid + 1]; i++) b[mid + 1][i] = 0;
    for (int i = w[mid + 1]; i <= 200; i++) b[mid + 1][i] = v[mid + 1];
    for (int i = mid + 2; i <= r; i++) {
        for (int j = 0; j < min(w[i], 201); j++) b[i][j] = b[i - 1][j];
        for (int j = w[i]; j <= 200; j++) b[i][j] = max(b[i - 1][j], b[i - 1][j - w[i]] + v[i]);
    }
    for (int i = ql; i <= qr; i++) tmp[i] = q[i];
    int cntl = ql, cntr = qr;
    for (int i = ql; i <= qr; i++) {
        if (tmp[i].r <= mid) q[cntl++] = tmp[i];
        else if (tmp[i].l > mid) q[cntr--] = tmp[i];
        else for (int j = 0; j <= tmp[i].t; j++) ans[tmp[i].id] = max(ans[tmp[i].id], s[tmp[i].l][j] + b[tmp[i].r][tmp[i].t - j]);
    }
    solve(l, mid, ql, cntl - 1);
    solve(mid + 1, r, cntr + 1, qr);
}

P6009 [USACO20JAN] Non-Decreasing Subsequences P

题意:给定 N 个不超过 K 的数,Q 次查询区间不下降子序列数,1\le N\le 50000,1\le K\le 20,1\le Q\le 200000。

简单 dp。设 S_{i,j} 表示 [i,mid] 中终点数值为 j 的不下降子序列数,B_{i,j} 表示 [mid,i] 中起点数值为 j 的不下降子序列数,均不包含空序列。

理论上可以去掉 j 直接计算所有不下降子序列数。为什么要这样设?因为合并时需要用到前一段的终点和后一段的起点,去掉 j 就无法合并了。

以 S 为例:

  1. 不选 a_i 的贡献:S_{i+1,j}。
  2. 只选 a_i 的贡献:1。
  3. 选 a_i 的贡献:需要再记录一个 t_{j,k},表示在 [i+1,mid] 中起点数值为 j、终点数值为 k 的不下降子序列数,那么贡献为 \sum_{k=a_i}^{j}t_{k,j}。
$B$ 的情况类似,即 $B_{i,j}=B_{i-1,j}+1+\sum_{k=j}^{a_i}t_{j,k}$,同时 $\forall j\in[1,a_i],\quad t_{a_i,j}\leftarrow t_{j,a_i}+S_{i,j}-S_{i-1,j}$。 查询时分为 $3$ 种贡献: 1. 空序列:$1$。 2. 只在 $mid$ 左右两侧的:$\sum_{i=1}^{K}S_{l,i}+\sum_{i=1}^{K}S_{r,i}$。 3. 跨过 $mid$ 的:$\sum_{i=1}^{K}\sum_{j=i}^{K}\left(S_{l,i}+B_{r,j}\right)$。 因此查询也是 $K^2$ 的,总复杂度为 $O(K^2N\log N+K^2Q)$。 其实 $t$ 可以用树状数组维护,从而降到 $\log K$,不过无所谓,他要是卡这常数那给他了( 代码如下: ```cpp int a[maxn], s[maxn][25], b[maxn][25], ans[maxn], t[25][25]; struct node { int l, r, id; } q[maxn], tmp[maxn]; void solve(int l, int r, int ql, int qr) { if (ql > qr) return; if (l == r) { for (int i = ql; i <= qr; i++) ans[q[i].id] = 2; return; } int mid = (l + r) >> 1; memset(t, 0, sizeof t), memset(s[mid], 0, sizeof s[mid]); s[mid][a[mid]] = 1, t[a[mid]][a[mid]] = 1; for (int i = mid - 1; i >= l; i--) { for (int j = 1; j <= 20; j++) s[i][j] = s[i + 1][j]; s[i][a[i]]++; for (int j = a[i]; j <= 20; j++) for (int k = a[i]; k <= j; k++) (s[i][j] += t[k][j]) %= mod; for (int k = a[i]; k <= 20; k++) (t[a[i]][k] += (s[i][k] - s[i + 1][k] + mod) % mod) %= mod; } memset(t, 0, sizeof t), memset(b[mid + 1], 0, sizeof b[mid + 1]); b[mid + 1][a[mid + 1]] = 1, t[a[mid + 1]][a[mid + 1]] = 1; for (int i = mid + 2; i <= r; i++) { for (int j = 1; j <= 20; j++) b[i][j] = b[i - 1][j]; b[i][a[i]]++; for (int j = 1; j <= a[i]; j++) for (int k = j; k <= a[i]; k++) (b[i][j] += t[j][k]) %= mod; for (int j = 1; j <= a[i]; j++) (t[j][a[i]] += (b[i][j] - b[i - 1][j] + mod) % mod) %= mod; } for (int i = ql; i <= qr; i++) tmp[i] = q[i]; int cntl = ql, cntr = qr; for (int i = ql; i <= qr; i++) { if (tmp[i].r <= mid) q[cntl++] = tmp[i]; else if (tmp[i].l > mid) q[cntr--] = tmp[i]; else { int res = 1; for (int j = 1; j <= 20; j++) (res += s[tmp[i].l][j]) %= mod; for (int k = 1; k <= 20; k++) (res += b[tmp[i].r][k]) %= mod; for (int j = 1; j <= 20; j++) for (int k = j; k <= 20; k++) (res += s[tmp[i].l][j] * b[tmp[i].r][k] % mod) %= mod; ans[tmp[i].id] = res; } } solve(l, mid, ql, cntl - 1); solve(mid + 1, r, cntr + 1, qr); } ``` ## 习题 [P7811 [JRKSJ R2] 你的名字。](https://www.luogu.com.cn/problem/P7811) [P17609 「RiOI-8」氷上 メルル](https://www.luogu.com.cn/problem/P17609) [P11882 [RMI 2024] 彩虹糖 / Skittlez](https://www.luogu.com.cn/problem/P11882) 完美挑战曲出现了: [P14513 [NFLSPC #8] 追忆 desuwa](https://www.luogu.com.cn/problem/P14513) [P6109 [Ynoi2009] rprmq1](https://www.luogu.com.cn/problem/P6109) [P17694 主旋律](https://www.luogu.com.cn/problem/P17694) 使用猫树/猫树分治写出来上面三道题的,可以找康神领一份酱味大鸡(