题意概述

给定按照题面规则建立出的线段树。

这棵树的叶子节点恰好对应原数组的 $n$ 个位置。对于任意一个叶子节点非空子集 $S$，记 $\operatorname{lca}(S)$ 为这些叶子的最近公共祖先节点编号。

我们要求：

$$\sum_{S \ne \varnothing} \operatorname{lca}(S)$$

其中 $S$ 遍历所有叶子节点的非空子集，答案对 $998244353$ 取模。

第一步：把“对子集求和”改写成“对节点求贡献”

设某个节点对应的区间长度为 $len$。

如果我们固定一个节点 $v$，那么有多少个叶子子集 $S$ 满足：

$$\operatorname{lca}(S)=v$$

这个数量只和 $v$ 对应区间的长度有关，和它在整棵树中的具体位置无关。

记这个值为 $w(len)$。

$1$．叶子节点

若 $len=1$，该节点本身就是一个叶子，只有唯一一个集合 $\{v\}$，因此：

$$w(1)=1$$

$2$．内部节点

若 $len>1$，设左子区间长度为：

$$L=\left\lceil \frac{len}{2} \right\rceil$$

右子区间长度为：

$$R=\left\lfloor \frac{len}{2} \right\rfloor$$

要使最近公共祖先恰好是当前节点，那么子集必须：

• 在左子树中至少选一个叶子；
• 在右子树中至少选一个叶子。

因此：

$$w(len)=(2^L-1)(2^R-1)$$

于是原式可以改写为：

$$\sum_{\text{节点 } v} \bigl(\text{label}(v)\bigr)\cdot w(\text{len}(v)) $$

也就是说，我们不必真的枚举子集，只要把每个节点的编号乘上“有多少个子集以它为 LCA”的系数即可。

第二步：为什么可以按深度压缩

这题最关键的地方是：虽然整棵树节点很多，但真正需要区分的信息很少。

性质 $1$：同一深度的节点，最高位完全相同

根节点编号为 $1$。

往左儿子走，编号变成 $2v$；往右儿子走，编号变成 $2v+1$。

因此深度为 $d$ 的所有节点，编号都恰好有 $d+1$ 个二进制位，最高位都等于：

$$2^d$$

所以如果我们只想统计“最高位”的贡献，那么同一深度的所有节点可以一起算。

性质 $2$：同一深度的区间长度至多只有两种

初始长度为 $n$。每次分裂后，一个长度 $x$ 的节点会变成：

$$\left\lceil \frac{x}{2} \right\rceil,\quad \left\lfloor \frac{x}{2} \right\rfloor $$

它们要么相等，要么只差 $1$。

继续向下递归后，同一深度的区间长度始终只会出现至多两种连续整数。

因此，我们不需要枚举这一层的所有节点，只需要记录：

• 某种区间长度是多少；
• 这种长度的节点有多少个；
• 这种长度对应的 $w(len)$ 是多少。

这正是标程里 find_ranges 维护的信息。

find_ranges(n) 到底返回了什么

为了便于理解，我们把代码中的参数 lg 看作真正的区间长度 $n$。

函数 find_ranges(n) 返回一个按深度分组的数组：

$$\text{find\_ranges}(n)[d]$$

表示深度 $d$ 这一层出现的所有“区间长度种类”。

其中每个三元组：

$$(\text{size},\text{cnt},\text{ways})$$

分别表示：

• size：这一类节点的区间长度；
• cnt：这一层里这种长度的节点个数；
• ways：也就是 $w(\text{size})$。

递归构造方式

当前长度为 $n$ 时：

1. 当前根节点本身对应一个三元组：

$$(n,1,w(n))$$

2. 左子树长度为 $\left\lceil \dfrac{n}{2} \right\rceil$，右子树长度为 $\left\lfloor \dfrac{n}{2} \right\rfloor$。

3. 左右子树递归得到的所有层，都整体下移一层。

4. 如果同一层中出现相同的 size，就把 cnt 合并。

由于总深度只有 $O(\log n)$，每一层的“长度种类数”又是常数级，所以整个过程是 $O(\log^2 n)$ 的。

第三步：先计算所有节点编号的最高位贡献

设：

$$C(n,\text{coef})$$

表示一棵长度为 $n$ 的线段树中，所有节点编号的最高位贡献之和，并且整体再乘一个系数 coef。

因为深度为 $d$ 的节点最高位都是 $2^d$，所以：

$$C(n,\text{coef}) = \sum_{d\ge 0} 2^d \cdot \text{coef}\cdot \sum_{(\text{size},\text{cnt},\text{ways}) \in \text{find\_ranges}(n)[d]} \text{cnt}\cdot \text{ways} $$

这正是函数 count(n, coef) 在做的事情。

对应代码：

Mint count(int lg, int coef)
{
    vector<vector<tuple<int, int, int>>> adam = find_ranges(lg);
    Mint ans = 0;
    Mint pow_2 = 1;
    for (int i = 0; i < (int)adam.size(); ++i)
    {
        for (auto [size, cnt, ways] : adam[i])
        {
            ans = ans + pow_2 * coef * cnt * ways;
        }
        pow_2 = pow_2 * 2;
    }
    return ans;
}

这里的 pow_2 就是当前深度的最高位 $2^d$。

第四步：更低位为什么只需要递归到“右儿子”

现在我们已经算出了每个节点编号的最高位。

那第二高位、第三高位、……怎么办？

关键观察是：

一个节点编号的二进制表示，去掉最高位后，后面的每一位都对应“从根往下走时，在某一层究竟走左还是走右”。

• 走左儿子，相当于这一位是 $0$；
• 走右儿子，相当于这一位是 $1$。

所以，某一位什么时候会产生贡献？

答案是：当且仅当我们在对应那一层走进了某个节点的右子树。

为什么走进右子树后，可以再次调用 count

设当前节点区间长度为 $len$，它的右子树长度为：

$$\left\lfloor \frac{len}{2} \right\rfloor$$

只要我们已经确定“这一位取 $1$”，那么后面更低的那些位如何分布，只和这个右子树内部的结构有关。

而右子树内部的编号后缀分布，和一棵新的、长度为 $\left\lfloor \dfrac{len}{2} \right\rfloor$ 的线段树完全同构。

也就是说，这个右子树里所有更低位的贡献，正好就是：

$$C\left(\left\lfloor \frac{len}{2} \right\rfloor,1\right) $$

如果这种长度的父节点一共有 cnt 个，那么就乘上 cnt，变成：

$$C\left(\left\lfloor \frac{len}{2} \right\rfloor,\text{cnt}\right) $$

这就是主函数里这一段的含义：

for (int i = 1; i < (int)adam.size(); ++i)
{
    for (auto [size, cnt, ways] : adam[i - 1])
    {
        int lsize = (size + 1) / 2;
        int rsize = size / 2;
        if (rsize)
        {
            ans = ans + count(rsize, cnt);
        }
    }
}

注意这里虽然也算了 lsize，但实际上只有 rsize 被使用，因为走到左儿子时新增的那一位是 $0$，不会贡献任何值。

整体算法

现在我们就能得到完整做法了：

1. 用 find_ranges(n) 压缩出每一层出现的区间长度种类与个数。
2. 先用 count(n, 1) 统计所有节点编号最高位的贡献。
3. 枚举所有节点种类，把每个节点的右子树看成“下一位取 $1$ 后的新问题”，加入 count(rsize, cnt)。
4. 累加后即为答案。

正确性说明

性质 $1$

对于任意一个区间长度为 $len$ 的节点，满足 $\operatorname{lca}(S)=v$ 的叶子子集个数只与 $len$ 有关，记为 $w(len)$。

其中：

• $w(1)=1$；
• 若 $len>1$，则

$$w(len)=\left(2^{\lceil len/2\rceil}-1\right)\left(2^{\lfloor len/2\rfloor}-1\right) $$

这是因为要让 LCA 恰好为当前节点，必须在左右子树中都至少选一个叶子。

性质 $2$

原问题的答案等于：

$$\sum_{\text{节点 } v} \text{label}(v)\cdot w(\text{len}(v)) $$

因此只需要对每个节点独立计算它的编号贡献即可。

性质 $3$

同一深度的所有节点最高位都相同，都是 $2^d$；并且同一深度的区间长度至多只有两种。

因此在统计最高位贡献时，按“深度 + 区间长度”压缩统计不会遗漏，也不会重复。

性质 $4$

对一个节点来说，除最高位外，其余每一位都对应根到该节点路径上的某一次左右选择。其中只有走向右儿子时，该位才为 $1$。

一旦固定在某一层走进右儿子，后面剩余更低位的分布就与这棵右子树内部的节点编号后缀完全一致，而这又与一个规模为右子树长度的子问题同构。

因此，对每个节点的右子树加入一次 count(rsize, cnt)，恰好计算了所有非最高位的贡献，而且每一位都被计算一次且仅计算一次。

结论

算法把每个节点编号的每一个二进制位贡献都准确统计了一次，并且都乘上了正确的 $w(len)$ 权重，因此最终得到的答案正确。

标程逐段解释

Mint

模数类，负责在 $998244353$ 下做加减乘。

powmod

快速幂，计算：

$$2^k \bmod 998244353$$

从而得到每种区间长度对应的：

$$w(len)$$

find_ranges

递归地构造每一层的所有长度种类。

其中：

Mint x = (powmod(2, (lg + 1) / 2) - 1) * (powmod(2, lg / 2) - 1);
ans[0].push_back({lg, 1, x.val});

就是在加入当前根节点这一级的三元组：

$$(len,1,w(len))$$

随后把左右子树的结果整体下移一层并合并。

count

按照深度把最高位 $2^d$ 累乘上去，统计某棵树所有节点编号的最高位贡献。

主函数

先做：

Mint ans = count(n, 1);

表示先把所有节点的最高位贡献都算出来。

然后：

for (int i = 1; i < (int)adam.size(); ++i)
{
    for (auto [size, cnt, ways] : adam[i - 1])
    {
        int rsize = size / 2;
        if (rsize)
        {
            ans = ans + count(rsize, cnt);
        }
    }
}

把所有“在某一层走向右儿子”所产生的更低位贡献补上。

复杂度分析

整棵树的深度是：

$$O(\log n)$$

find_ranges(n) 需要维护 $O(\log n)$ 层信息，每层的长度种类数是常数级，因此总复杂度为：

$$O(\log^2 n)$$

count(n, coef) 也只会遍历这些压缩后的层信息，因此也是：

$$O(\log^2 n)$$

整份标程每组数据的总时间复杂度为：

$$O(\log^2 n)$$

空间复杂度为：

$$O(\log^2 n)$$

在 $n \le 10^{18}$ 的条件下完全可以通过。

参考代码

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int mod = 998244353;
struct Mint
{
    int val;
    Mint(long long x = 0)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator*(Mint oth)
    {
        return val * oth.val;
    }
};
Mint powmod(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 1)
    {
        return powmod(a, b - 1) * a;
    }
    Mint P = powmod(a, b / 2);
    return P * P;
}
map<int, vector<vector<tuple<int, int, int>>>> memo;
vector<vector<tuple<int, int, int>>> find_ranges(int lg) // log^2
{
    if (memo.find(lg) != memo.end())
    {
        return memo[lg];
    }
    if (lg == 1)
    {
        return {{{1, 1, 1}}};
    }
    vector<vector<tuple<int, int, int>>> l = find_ranges((lg + 1) / 2);
    vector<vector<tuple<int, int, int>>> r = find_ranges(lg / 2);
    vector<vector<tuple<int, int, int>>> ans(max(l.size(), r.size()) + 1);
    Mint x = (powmod(2, (lg + 1) / 2) - 1) * (powmod(2, lg / 2) - 1);
    ans[0].push_back({lg, 1, x.val});
    for (int i = 0; i < (int)l.size(); ++i)
    {
        for (auto j : l[i])
        {
            ans[i + 1].push_back(j);
        }
    }
    for (int i = 0; i < (int)r.size(); ++i)
    {
        for (auto j : r[i])
        {
            bool ok = false;
            for (auto &[size, cnt, ways] : ans[i + 1])
            {
                if (size == get<0>(j))
                {
                    ok = true;
                    cnt += get<1>(j);
                }
            }
            if (!ok)
            {
                ans[i + 1].push_back(j);
            }
        }
    }
    return memo[lg] = ans;
}
Mint count(int lg, int coef)
{
    vector<vector<tuple<int, int, int>>> adam = find_ranges(lg);
    Mint ans = 0;
    Mint pow_2 = 1;
    for (int i = 0; i < (int)adam.size(); ++i)
    {
        for (auto [size, cnt, ways] : adam[i])
        {
            ans = ans + pow_2 * coef * cnt * ways;
        }
        pow_2 = pow_2 * 2;
    }
    return ans;
}
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<vector<tuple<int, int, int>>> adam = find_ranges(n);
        Mint ans = count(n, 1);
        for (int i = 1; i < (int)adam.size(); ++i)
        {
            for (auto [size, cnt, ways] : adam[i - 1])
            {
                int lsize = (size + 1) / 2;
                int rsize = size / 2;
                if (rsize)
                {
                    ans = ans + count(rsize, cnt);
                }
            }
        }
        cout << ans.val << '\n';
        memo.clear();
    }
}