静态树上 n log log n 复杂度的路径结合信息查询

Gcysnd · 2026-10-05 22:30:27 · 算法·理论

前言

:::info[免责声明] 在目前已查找到的算法中，还没有发现与本算法在 O(n\log\log n) 空间下具有相同最坏查询复杂度的树路径查询结构。若本算法并非首个，或复杂度分析存在纰漏，说明我太菜。 :::

树链剖分

那你在树链剖分上套个 Sqrt Tree 不就这个复杂度。

考虑剖分成 O(\log n) 条重链，很难保证维护复杂度不是 O((\log n) \cdot (\log \log n))，除非你非常的强可以把一棵树只用一条重链表示。

Top-cluster 分割

树剖没有前途，考虑从根（号算法）源解决问题。先看树分块。

Top-cluster 分割采用 top-tree 风格的边划分。它将一棵树分为若干簇，保证：

• 每个簇是原树的一棵连通子树；
• 不同簇的边集交集为空；
• 每个簇内至多有两个点与簇外点相连，这些点称为边界点；
• 边界点可以同时属于多个簇。

在这一意义下，Top-cluster 分割可将一棵 n 个节点的树分为 O(n/B) 个簇，每个簇的大小为 O(B)。取 B=\sqrt n，则簇数为 O(\sqrt n)。

为了代码实现的方便，通常强制节点 1 为根且其为边界点。约定上界点为有根树上深度浅的，下界点为深度深的。

递归分块

设当前块为 C，其大小为 s=|C|。取 B=\sqrt{s}。然后对 C 做 Top-cluster 分割，得到若干子簇 C_1,C_2,\dots,C_M，其中：

且每个子簇大小 O(B)。

对每个子簇内部递归执行同样的分割。由此得到一棵递归块树。由 Sqrt Tree 的理论得到总共 O(\log \log n) 层。每一层 T_i 是由该层所有块中的原节点副本组成的森林。由于每个块大小之和为 O(n)，边界点副本总数也为 O(n)，所以每层森林总节点数为 O(n)。

因此总空间为 O(n\log\log n)。

:::info[粗略证明如下]

每一层是其上层结构的一个森林，令其上层规模为 x，则该层被分为 O(\sqrt x) 个块。分块的终止条件是 x=1，因此设原树 T_0 的规模为 n，每层递归缩减 \sqrt n，因此我们的层数 O(\log \log n)。

每层森林规模是 O(n)，总复杂度 O(n \log \log n)。

:::

树上 Prefix / Suffix

在每一层 T_i 中，对每个块 C，设其边界点为 b_0,b_1，若只有一个边界点则令 b_0=b_1。

对每个节点 x\in C，定义如下 Sqrt Tree 状物：

若所维护的操作 \oplus 不可交换，则还需存储反向答案，方便你查从 u 到 v 的路径和从 v 到 u 的路径：

每个节点每个块副本只存 O(1) 个值。每层总节点数为 O(n)，层数为 O(\log\log n)，故这部分空间为 O(n\log\log n)。这一点和 Sqrt Tree 差不多的。

块间 Between

对每一层的每个父块 C，设其子簇为 C_1,C_2,\dots,C_M，其中：

定义 between_{i,j} 为从子簇 C_i 的某个出口边界点到子簇 C_j 的某个入口边界点的路径答案，并记录对应的出口、入口边界点编号。然后由于 M=O(\sqrt{s})，所以 O(M^2)=O(s)。所有父块求和，每层总存储为 O(n)。层数为 O(\log\log n)，因此这部分空间为 O(n\log\log n)。

查询算法

查询原树上的路径 (u,v)。从根块开始递归。

设当前块为 C。若 u 和 v 在 C 的同一个子簇 C_i 中，则直接递归进入 C_i。

否则，设：

在父块 C 的 between 表中取出 between_{i,j}，它给出了从 C_i 的出口边界点 a 到 C_j 的入口边界点 b 的答案。

然后合并三段：

其中：

若 u,v 一直处于同一个子簇中，则不断下钻，直到块大小为 O(1)，此时暴力计算，代价 O(1)。

每层判断为 O(1)，层数为 O(\log\log n)。所以总查询时间复杂度为 O(\log\log n)。

可能的优化

朴素 Sqrt Tree 把序列拆成 2^k 长度在这里显然无用，你无法保证你的各各簇内全都是严格 2^k 大小来套用二进制优化。

但是我们想到下钻的过程实际上很烦人，而且下钻的过程是具有单调性的：若本簇覆盖树上路径，则父簇也一定覆盖树上路径；若本簇不完全覆盖查询的树上路径，则其子簇也不能覆盖。

不妨用数组开个映射，存储每个点对应哪些簇。对于界点特殊处理一下。就可以查询该点在不在对应簇中。

因此设最终查询所在的森林是 T_x，可以二分这个 x 来把查询复杂度优化到 O(\log \log \log n)。

适用条件

• 所维护的操作 \oplus 需要满足结合律；
• 若 \oplus 不可交换，则所有 pre,suf,between 都需按路径方向存储和合并；
• Top-cluster 分割需采用边划分，并允许边界点共享。不然星型树只能受着了。

一些实现细节

注意到预处理 pre,suf,between 实际上就是在某一层的收缩树上跑暴力跳或者在块内暴力跳，所以码量可能并没有想象的那么大。吗？

我的答案是：\geq 500 行，哦哦哦哦哦哦哦哦哦原来是码量大的实现杂的常数因子大的，跑的肯定不快。

对拍结果

共进行 6 次对拍，每次对拍的树形不同。其中，该算法和 Top-cluster 树分块的输出均一致。

以下是同数据评测，树规模 n=10^5，询问规模 m=10^6。计时取 m 次询问的平均值。保证：

• 计时采用 std::chrono::steady_clock。
• 每次询问均匀随机生成。
• 本算法代码采用 O(\log \log n) 询问的实现方式。
• 操作采用典型的结合操作 \min。

因此，在随机数据下，本算法在考虑常数的情况下已经做到几乎碾压一般树分块。在构造数据下，树分块只有可能被卡得更惨。

实现代码

这版代码使用 AI 优化过。保障本人对该代码的贡献超过 AI。

:::info[OCT.hpp]

#pragma once#include<bits/stdc++.h>

#ifndef TCT_LEAF
#define TCT_LEAF 4
#endif
namespace tct {
    struct MinOp {
        using T = int;
        static T id() {
            return INT_MAX;
        }
        static T op(const T & a,
            const T & b) {
            return a < b ? a : b;
        }
    };
    template < class Op >
        class TopClusterTree {
            public: using Item = typename Op::T;
            struct Seg {
                Item f, b;
            };
            struct Stats {
                long long blocks = 0;
                long long clusterCount = 0;
                long long preSufEntries = 0;
                long long betweenEntries = 0;
                long long maxBetweenPerBlock = 0;
                int maxClusterSize = 0;
                int maxDepth = 0;
            };
            void init(int n,
                const std::vector < Item > & value,
                    const std::vector < std::pair < int, int >> & edges);
            Item query(int u, int v) const;
            void dump(std::ostream & os) const {
                os << "blocks=" << blocks.size() << "\n";
                for (size_t b = 0; b < blocks.size(); b++) {
                    const Block & B = blocks[b];
                    os << "block " << b << ": t=" << B.t << " s=" << B.s << " nv=" << B.nv << (B.leaf ? " LEAF" : "") << "\n";
                    for (int k = 0; k < B.clCnt; k++) {
                        const Cluster & c = clG[B.clOff + k];
                        int cb = clBlockG[B.clBlockOff + k];
                        os << "  cluster " << k << ": t=" << c.t << " s=" << c.s << " nv=" << blocks[cb].nv << "\n";
                    }
                }
            }
            Stats stats;
            private: static constexpr int LEAF = TCT_LEAF;
            struct Cluster {
                int t, s;
            };
            struct Entry {
                int a, b;
                Seg seg;
            };
            struct Block {
                int t = 0, s = 0, nv = 0;
                bool leaf = false;
                int preOff = 0, sufOff = 0, subOff = 0, childOff = 0;
                int clOff = 0, clCnt = 0, clBlockOff = 0, betweenOff = 0;
            };
            int n = 0;
            std::vector < Item > val;
            std::vector < int > fa,
            dep;
            std::vector < std::vector < int >> adj;
            std::vector < int > pos;
            std::vector < int > rootPos;
            std::vector < Block > blocks;
            std::vector < Seg > preG,
            sufG;
            std::vector < int > subG,
            childG;
            std::vector < int > clBlockG;
            std::vector < Cluster > clG;
            std::vector < Entry > betG;
            std::vector < int > ptId;
            static Seg cat(const Seg & x,
                const Seg & y) {
                return Seg {
                    Op::op(x.f, y.f), Op::op(y.b, x.b)
                };
            }
            static Seg rev(const Seg & x) {
                return Seg {
                    x.b, x.f
                };
            }
            static Seg one(const Item & v) {
                return Seg {
                    v,
                    v
                };
            }
            static Seg ident() {
                return Seg {
                    Op::id(), Op::id()
                };
            }
            int buildBlock(std::vector < int > verts, int t, int s, bool isRoot, int depth);
            Item brute(int u, int v) const;
        };
    template < class Op >
        void TopClusterTree < Op > ::init(int n_,
            const std::vector < Item > & a,
                const std::vector < std::pair < int, int >> & edges) {
            n = n_;
            val.assign(n + 1, Op::id());
            for (int i = 1; i <= n; i++) val[i] = a[i];
            adj.assign(n + 1, {});
            for (auto & e: edges) {
                adj[e.first].push_back(e.second);
                adj[e.second].push_back(e.first);
            }
            fa.assign(n + 1, 0);
            dep.assign(n + 1, 0);
            std::vector < int > order;
            order.reserve(n);
            order.push_back(1);
            fa[1] = 0;
            dep[1] = 0;
            for (size_t i = 0; i < order.size(); i++) {
                int u = order[i];
                for (int w: adj[u]) {
                    if (w == fa[u]) continue;
                    fa[w] = u;
                    dep[w] = dep[u] + 1;
                    order.push_back(w);
                }
            }
            pos.assign(n + 1, -1);
            ptId.assign(n + 1, -1);
            rootPos.assign(n + 1, -1);
            blocks.clear();
            preG.clear();
            sufG.clear();
            subG.clear();
            childG.clear();
            clBlockG.clear();
            clG.clear();
            betG.clear();
            stats = Stats();
            buildBlock(std::move(order), 1, 1, true, 0);
        }
    template < class Op >
        int TopClusterTree < Op > ::buildBlock(std::vector < int > verts, int t, int s, bool isRoot, int depth) {
            const int sz = (int) verts.size();
            const int bid = (int) blocks.size();
            blocks.emplace_back();
            for (int i = 0; i < sz; i++) pos[verts[i]] = i;
            std::vector < int > parL(sz, -1), head(sz, -1), nxt(sz, -1);
            for (int i = 0; i < sz; i++) {
                int x = verts[i];
                if (i == pos[t]) continue;
                int p = pos[fa[x]];
                parL[i] = p;
                nxt[i] = head[p];
                head[p] = i;
            }
            Block NB;
            NB.t = t;
            NB.s = s;
            NB.nv = sz;
            NB.preOff = NB.sufOff = -1;
            if (!isRoot) {
                NB.preOff = (int) preG.size();
                NB.sufOff = (int) sufG.size();
                preG.resize(preG.size() + sz);
                sufG.resize(sufG.size() + sz);
                auto dfsFrom = [ & ](int startLocal, std::vector < Seg > & out, int off) {
                    std::vector < std::pair < int, int >> st;
                    st.reserve(sz);
                    st.push_back({
                        startLocal,
                        -1
                    });
                    out[off + startLocal] = ident();
                    while (!st.empty()) {
                        int i = st.back().first, p = st.back().second;
                        st.pop_back();
                        Seg su = out[off + i];
                        for (int c = head[i]; c != -1; c = nxt[c]) {
                            if (c == p) continue;
                            out[off + c] = cat(su, one(val[verts[c]]));
                            st.push_back({
                                c,
                                i
                            });
                        }
                        if (parL[i] != -1 && parL[i] != p) {
                            out[off + parL[i]] = cat(su, one(val[verts[parL[i]]]));
                            st.push_back({
                                parL[i],
                                i
                            });
                        }
                    }
                };
                dfsFrom(pos[t], preG, NB.preOff);
                dfsFrom(pos[s], sufG, NB.sufOff);
            }
            std::vector < std::vector < int >> cVerts;
            std::vector < std::pair < int, int >> cTS;
            bool leaf = (sz <= LEAF);
            if (!leaf) {
                int B = (int) std::sqrt((double) sz);
                while (B * B < sz) B++;
                if (B < 2) B = 2;
                std::vector < int > ord;
                ord.reserve(sz);
                {
                    std::vector < int > st;
                    st.push_back(pos[t]);
                    while (!st.empty()) {
                        int i = st.back();
                        st.pop_back();
                        ord.push_back(verts[i]);
                        for (int c = head[i]; c != -1; c = nxt[c]) st.push_back(c);
                    }
                }
                assert((int) ord.size() == sz);
                std::vector < int > szv(sz, 0), cont(sz, 0);
                std::vector < char > isB(sz, 0);
                auto collectPending = [ & ](int i0, std::vector < int > & cv) {
                    std::vector < int > st;
                    st.push_back(i0);
                    while (!st.empty()) {
                        int i = st.back();
                        st.pop_back();
                        cv.push_back(verts[i]);
                        if (isB[i]) continue;
                        for (int c = head[i]; c != -1; c = nxt[c]) st.push_back(c);
                    }
                };
                for (int oi = sz - 1; oi >= 0; oi--) {
                    int u = ord[oi];
                    int lu = pos[u];
                    int sum = 1, cnt = 0, cc = -1;
                    for (int c = head[lu]; c != -1; c = nxt[c]) {
                        sum += szv[c];
                        if (cont[c]) {
                            cnt++;
                            cc = c;
                        }
                    }
                    bool bnd = (u == t) || (sum > B) || (cnt > 1);
                    if (!bnd) {
                        szv[lu] = sum;
                        cont[lu] = (cnt == 1) ? cont[cc] : 0;
                        continue;
                    }
                    isB[lu] = 1;
                    int curSize = 1, curCont = 0;
                    std::vector < int > grp;
                    auto flush = [ & ]() {
                        if (grp.empty()) return;
                        int sC = curCont ? curCont : u;
                        std::vector < int > cv;
                        cv.push_back(u);
                        for (int c: grp) collectPending(c, cv);
                        cVerts.push_back(std::move(cv));
                        cTS.push_back({
                            u,
                            sC
                        });
                        grp.clear();
                        curSize = 1;
                        curCont = 0;
                    };
                    for (int c = head[lu]; c != -1; c = nxt[c]) {
                        if (curCont && cont[c]) flush();
                        if (!grp.empty() && curSize + szv[c] > B) flush();
                        curSize += szv[c];
                        grp.push_back(c);
                        if (cont[c]) curCont = cont[c];
                    }
                    flush();
                    szv[lu] = 1;
                    cont[lu] = u;
                }
                #ifdef TCT_DEBUG {
                    std::vector < int > inC(sz, -1), owner(sz, -1), mark(sz, -1);
                    for (int k = 0; k < (int) cVerts.size(); k++) {
                        int tk = cTS[k].first, sk = cTS[k].second;
                        int m = (int) cVerts[k].size();
                        for (int x: cVerts[k]) inC[pos[x]] = k;
                        int cntv = 1;
                        std::vector < int > st;
                        st.push_back(pos[tk]);
                        mark[pos[tk]] = k;
                        while (!st.empty()) {
                            int i = st.back();
                            st.pop_back();
                            for (int c = head[i]; c != -1; c = nxt[c]) {
                                if (inC[c] != k || mark[c] == k) continue;
                                mark[c] = k;
                                cntv++;
                                st.push_back(c);
                            }
                            int p = parL[i];
                            if (p != -1 && inC[p] == k && mark[p] != k) {
                                mark[p] = k;
                                cntv++;
                                st.push_back(p);
                            }
                        }
                        assert(cntv == m);
                        for (int x: cVerts[k]) mark[pos[x]] = -1;
                        for (int x: cVerts[k]) {
                            if (x == tk) continue;
                            int lx = pos[x];
                            assert(owner[lx] == -1);
                            owner[lx] = k;
                        }
                        std::vector < int > bv;
                        for (int x: cVerts[k]) {
                            int i = pos[x];
                            if (parL[i] != -1 && inC[parL[i]] != k) bv.push_back(x);
                            for (int c = head[i]; c != -1; c = nxt[c])
                                if (inC[c] != k) bv.push_back(x);
                        }
                        std::sort(bv.begin(), bv.end());
                        bv.erase(std::unique(bv.begin(), bv.end()), bv.end());
                        assert((int) bv.size() <= 2);
                        for (int x: bv) assert(x == tk || x == sk);
                        for (int x: cVerts[k]) inC[pos[x]] = -1;
                    }
                    for (int i = 0; i < sz; i++)
                        if (i != pos[t]) assert(owner[i] != -1);
                }
                #endif
                if ((int) cTS.size() == 1 && (int) cVerts[0].size() == sz) {
                    assert(sz <= LEAF);
                    cVerts.clear();
                    cTS.clear();
                    leaf = true;
                }
                if (cTS.empty()) leaf = true;
            }
            NB.leaf = leaf;
            const int M = (int) cTS.size();
            NB.clOff = (int) clG.size();
            NB.clCnt = M;
            for (int k = 0; k < M; k++) clG.push_back(Cluster {
                cTS[k].first, cTS[k].second
            });
            NB.subOff = (int) subG.size();
            NB.childOff = (int) childG.size();
            subG.resize(subG.size() + sz, -1);
            childG.resize(childG.size() + sz, -1);
            std::vector < int > idxS(M, -1);
            for (int k = 0; k < M; k++) {
                int tk = cTS[k].first, sk = cTS[k].second;
                auto & cv = cVerts[k];
                for (int i = 0; i < (int) cv.size(); i++) {
                    int x = cv[i];
                    if (x == tk) {
                        if (x == sk) idxS[k] = i;
                        continue;
                    }
                    subG[NB.subOff + pos[x]] = k;
                    childG[NB.childOff + pos[x]] = i;
                    if (x == sk) idxS[k] = i;
                }
            } {
                int lt = pos[t];
                if (subG[NB.subOff + lt] < 0) {
                    for (int k = 0; k < M; k++)
                        if (cTS[k].first == t) {
                            subG[NB.subOff + lt] = k;
                            childG[NB.childOff + lt] = 0;
                            break;
                        }
                }
            }
            NB.clBlockOff = (int) clBlockG.size();
            clBlockG.resize(clBlockG.size() + M, -1);
            for (int k = 0; k < M; k++)
                stats.maxClusterSize = std::max(stats.maxClusterSize, (int) cVerts[k].size());
            if (bid == 0)
                for (int i = 0; i < sz; i++) rootPos[verts[i]] = i;
            for (int x: verts) pos[x] = -1;
            std::vector < int > cb(M, -1);
            for (int k = 0; k < M; k++)
                cb[k] = buildBlock(std::move(cVerts[k]), cTS[k].first, cTS[k].second, false, depth + 1);
            for (int k = 0; k < M; k++) clBlockG[NB.clBlockOff + k] = cb[k];
            if (!leaf && M > 0) {
                std::vector < Seg > labF(M), labB(M);
                for (int k = 0; k < M; k++) {
                    const Block & CB = blocks[cb[k]];
                    labF[k] = preG[CB.preOff + idxS[k]];
                    labB[k] = sufG[CB.sufOff + 0];
                }
                std::vector < int > nodes;
                nodes.reserve(2 * M);
                std::vector < int > nT(M), nS(M);
                for (int k = 0; k < M; k++) {
                    int tt = cTS[k].first, ss = cTS[k].second;
                    if (ptId[tt] < 0) {
                        ptId[tt] = (int) nodes.size();
                        nodes.push_back(tt);
                    }
                    if (ptId[ss] < 0) {
                        ptId[ss] = (int) nodes.size();
                        nodes.push_back(ss);
                    }
                    nT[k] = ptId[tt];
                    nS[k] = ptId[ss];
                }
                const int V = (int) nodes.size();
                std::vector < std::vector < std::pair < int, int >>> pg(V);
                int ecnt = 0;
                for (int k = 0; k < M; k++)
                    if (nT[k] != nS[k]) {
                        pg[nT[k]].push_back({
                            nS[k],
                            k
                        });
                        pg[nS[k]].push_back({
                            nT[k],
                            k
                        });
                        ecnt++;
                    }
                assert(ecnt == V - 1);
                std::vector < int > tin(V, -1), tout(V, -1), par(V, -1), it(V, 0);
                const int rootN = ptId[t];
                {
                    int timer = 0;
                    std::vector < int > st;
                    st.push_back(rootN);
                    par[rootN] = rootN;
                    tin[rootN] = timer++;
                    while (!st.empty()) {
                        int u = st.back();
                        if (it[u] < (int) pg[u].size()) {
                            int v = pg[u][it[u]++].first;
                            if (par[v] < 0) {
                                par[v] = u;
                                tin[v] = timer++;
                                st.push_back(v);
                            }
                        } else {
                            tout[u] = timer - 1;
                            st.pop_back();
                        }
                    }
                    for (int i = 0; i < V; i++) assert(tin[i] >= 0);
                }
                auto isAnc = [ & ](int x, int y) {
                    return tin[x] <= tin[y] && tout[y] <= tout[x];
                };
                const size_t bo = betG.size();
                betG.resize(bo + (size_t) M * M);
                std::vector < Seg > row(V);
                std::vector < int > vis(V, -1);
                int epoch = 0;
                for (int i = 0; i < M; i++) {
                    int ti = cTS[i].first, si = cTS[i].second;
                    betG[bo + (size_t) i * M + i] = Entry {
                        ti,
                        ti,
                        ident()
                    };
                    for (int which = 0; which < 2; which++) {
                        int src = (which == 0) ? nT[i] : nS[i];
                        if (which == 1 && nS[i] == nT[i]) break;
                        ++epoch;
                        std::vector < int > st;
                        st.push_back(src);
                        vis[src] = epoch;
                        row[src] = ident();
                        while (!st.empty()) {
                            int u = st.back();
                            st.pop_back();
                            for (auto & pr: pg[u]) {
                                int v = pr.first, k = pr.second;
                                if (vis[v] == epoch) continue;
                                vis[v] = epoch;
                                row[v] = cat(row[u], (nodes[u] == cTS[k].first) ? labF[k] : labB[k]);
                                st.push_back(v);
                            }
                        }
                        for (int j = 0; j < M; j++) {
                            if (j == i) continue;
                            int tj = cTS[j].first, sj = cTS[j].second;
                            int a = (ti == si) ? ti : (isAnc(nS[i], nT[j]) ? si : ti);
                            int na = (a == ti) ? nT[i] : nS[i];
                            if (na != src) continue;
                            int b = (tj == sj) ? tj : (isAnc(nS[j], nT[i]) ? sj : tj);
                            int nb = (b == tj) ? nT[j] : nS[j];
                            betG[bo + (size_t) i * M + j] = Entry {
                                a,
                                b,
                                row[nb]
                            };
                        }
                    }
                }
                NB.betweenOff = (int) bo;
                for (int x: nodes) ptId[x] = -1;
                stats.maxBetweenPerBlock = std::max(stats.maxBetweenPerBlock, (long long) M * M);
            }
            blocks[bid] = NB;
            stats.blocks++;
            stats.clusterCount += M;
            stats.betweenEntries = (long long) betG.size();
            stats.preSufEntries = (long long) preG.size() + (long long) sufG.size();
            stats.maxDepth = std::max(stats.maxDepth, depth);
            return bid;
        }
    template < class Op >
        typename TopClusterTree < Op > ::Item TopClusterTree < Op > ::brute(int u, int v) const {
            int up[TCT_LEAF + 2], down[TCT_LEAF + 2];
            int cu = 0, cd = 0;
            while (dep[u] > dep[v]) {
                up[cu++] = u;
                u = fa[u];
            }
            while (dep[v] > dep[u]) {
                down[cd++] = v;
                v = fa[v];
            }
            while (u != v) {
                up[cu++] = u;
                u = fa[u];
                down[cd++] = v;
                v = fa[v];
            }
            assert(cu <= TCT_LEAF + 1 && cd <= TCT_LEAF + 1);
            Seg res = ident();
            for (int i = 0; i < cu; i++) res = cat(res, one(val[up[i]]));
            res = cat(res, one(val[u]));
            for (int i = cd - 1; i >= 0; i--) res = cat(res, one(val[down[i]]));
            return res.f;
        }
    template < class Op >
        typename TopClusterTree < Op > ::Item TopClusterTree < Op > ::query(int u, int v) const {
            if (u == v) return val[u];
            int bid = 0;
            int lu = rootPos[u], lv = rootPos[v];
            while (true) {
                const Block & B = blocks[bid];
                if (B.leaf) return brute(u, v);
                int cu = subG[B.subOff + lu];
                int cv = subG[B.subOff + lv];
                if (cu == cv) {
                    lu = childG[B.childOff + lu];
                    lv = childG[B.childOff + lv];
                    bid = clBlockG[B.clBlockOff + cu];
                    continue;
                }
                const Entry & e = betG[B.betweenOff + (size_t) cu * B.clCnt + cv];
                const int cbU = clBlockG[B.clBlockOff + cu];
                const int cbV = clBlockG[B.clBlockOff + cv];
                const Block & BU = blocks[cbU];
                const Block & BV = blocks[cbV];
                const int iu = childG[B.childOff + lu];
                const int iv = childG[B.childOff + lv];
                Seg res = (e.a == BU.t) ? rev(preG[BU.preOff + iu]) : rev(sufG[BU.sufOff + iu]);
                res = cat(res, one(val[e.a]));
                res = cat(res, e.seg);
                res = (e.b == BV.t) ? cat(res, preG[BV.preOff + iv]) : cat(res, sufG[BV.sufOff + iv]);
                return res.f;
            }
        }
}

:::

结语

:::info[AI/LLM 使用声明] 本文使用 DeepSeek v4.1-flash 优化 \LaTeX 和 Markdown。保证本人对本文及本算法的贡献超过 90\%。

码量大细节多，我调了两周才写出初版代码，理论意义远大于工程意义。