「线段树覆盖期望」题解

问题分析

我们需要计算：对于线段树的标准建树方式，随机选择一个区间 $[A,B]$，用线段树节点覆盖该区间所需的最少节点数 $cover(A,B)$ 的期望，乘以区间总数 $\frac{n(n+1)}{2}$，并对 $10^9+7$ 取模。

换句话说，我们需要计算：

$$S(n) = \sum_{1 \leq a \leq b \leq n} cover(a,b)$$

其中 $cover(a,b)$ 表示用线段树节点覆盖区间 $[a,b]$ 所需的最少节点数。

线段树覆盖的性质

1. 线段树的建树方式

对于节点 $[L,R]$，中点 $mid = \lfloor \frac{L+R}{2} \rfloor$，左子节点 $[L,mid]$，右子节点 $[mid+1,R]$。

这是一个标准的线段树建树方式。

2. $cover(a,b)$ 的定义

用线段树节点（即树上已有的区间节点）覆盖区间 $[a,b]$，要求：

• 覆盖的节点区间互不相交
• 它们的并集恰好是 $[a,b]$
• 节点数最少

这实际上就是线段树查询区间 $[a,b]$ 时访问的节点数。

关键性质：在标准线段树中，$cover(a,b)$ 等于查询区间 $[a,b]$ 时需要访问的节点数。更具体地说，是线段树区间查询算法中访问的节点数（不包括完全在查询区间外的节点）。

3. 线段树查询的节点数分析

对于查询区间 $[l,r]$，线段树递归查询：

• 如果当前节点区间完全包含于 $[l,r]$，则返回该节点（计数1）
• 否则，递归查询左右子节点

因此，$cover(l,r)$ 等于递归查询过程中访问的节点数，其中完全包含于 $[l,r]$ 的节点只计1次。

问题转化

我们需要计算所有区间 $[a,b]$ 的 $cover(a,b)$ 之和。

设线段树有 $N$ 个节点（$N = 2n-1$，对于满二叉树，但这里不一定是满二叉树）。

对于每个线段树节点 $[L,R]$，考虑它会对多少查询区间做出贡献。

观察：节点 $[L,R]$ 对查询区间 $[a,b]$ 有贡献（即 $cover(a,b)$ 包含该节点）当且仅当：

$$L \geq a \quad \text{且} \quad R \leq b$$

并且该节点在查询过程中被选中（即它是查询分解的一部分）。

但这还不够，因为一个节点被选中还需要满足：它的父节点没有被完全包含在查询区间中。

更精确的分析

1. 节点的贡献条件

对于节点 $u$ 表示区间 $[L,R]$：

• 它被选中当且仅当：
  1. $[L,R] \subseteq [a,b]$（完全包含在查询区间内）
  2. 父节点不被完全包含（否则会选择父节点而不是子节点）

等价地：存在查询区间 $[a,b]$ 使得 $u$ 被选中的条件是：

• $a \leq L$ 且 $R \leq b$
• 且要么 $a > L_{\text{parent}}$ 的左边界，要么 $b < R_{\text{parent}}$ 的右边界（其中 $[L_{\text{parent}}, R_{\text{parent}}]$ 是父节点区间）

2. 计算每个节点的贡献数

设节点 $u$ 表示区间 $[L,R]$，长度为 $len = R-L+1$。

父节点 $p$ 表示区间 $[L_p, R_p]$，其中：

• 如果 $u$ 是左孩子：$L_p = L$，$R_p = R + (R-L+1)$ 或类似
• 如果 $u$ 是右孩子：$L_p = L - (R-L+1)$，$R_p = R$

实际上，由于建树方式 $mid = \lfloor (L+R)/2 \rfloor$，左右子区间长度可能相差1。

关键：节点 $u$ 被选中当且仅当查询区间 $[a,b]$ 满足：

1. $a \leq L$ 且 $R \leq b$（包含 $u$）
2. 且不包含整个父节点区间

不包含整个父节点区间意味着：

• 如果 $u$ 是左孩子：$b < R_p$（即 $b < R_p$，因为 $a$ 已经 $\leq L_p = L$）
• 如果 $u$ 是右孩子：$a > L_p$（即 $a > L_p$，因为 $b$ 已经 $\geq R_p = R$）

3. 具体计算

设节点 $u=[L,R]$，长度为 $k = R-L+1$。

情况1：$u$ 是左孩子

• 父节点 $p=[L, R']$，其中 $R' > R$
• $u$ 被选中条件：$a \leq L$，$R \leq b < R'$
• 这样的 $(a,b)$ 对数：$L \times (R'-R)$

情况2：$u$ 是右孩子

• 父节点 $p=[L', R]$，其中 $L' < L$
• $u$ 被选中条件：$L' < a \leq L$，$R \leq b$
• 这样的 $(a,b)$ 对数：$(L-L') \times (n-R+1)$

根节点 $[1,n]$：总是被选中当查询区间为 $[1,n]$ 时，贡献1。

递归计算

我们可以递归计算所有节点的贡献。

定义 $f(L,R)$ 表示区间 $[L,R]$ 对应的节点对总和的贡献。

对于节点 $[L,R]$：

• 如果 $L=R$（叶节点）：总是被选中当查询区间为 $[L,L]$ 时

  • 贡献：1（只有区间 $[L,L]$ 会选中该叶节点）

• 如果 $L<R$： 设 $mid = \lfloor (L+R)/2 \rfloor$ 左孩子：$[L, mid]$ 右孩子：$[mid+1, R]$

  节点 $[L,R]$ 本身被选中的条件：查询区间包含 $[L,R]$ 但不包含父节点区间。但对于根节点 $[1,n]$，没有父节点，只有查询区间 $[1,n]$ 会选中它（贡献1）。

  对于非根节点，我们需要知道它是左孩子还是右孩子，但这在递归中自然确定。

更好的方法是：在递归过程中，我们知道当前区间 $[L,R]$ 和它的扩展区间（即如果不分裂，父节点会表示的区间）。

另一种思路：直接计算总和

设 $T(n) = \sum_{1 \leq a \leq b \leq n} cover(a,b)$

我们想找到 $T(n)$ 的递推公式。

考虑线段树的分裂点

对于区间 $[1,n]$，中点 $m = \lfloor (1+n)/2 \rfloor$

线段树分裂为：

• 左子树：区间 $[1, m]$
• 右子树：区间 $[m+1, n]$

对于查询区间 $[a,b]$：

• 如果 $a \leq m < b$：区间跨越中点，需要分别查询左右子树
• 如果 $b \leq m$：区间完全在左子树
• 如果 $a > m$：区间完全在右子树

递推公式

$cover(a,b)$ 的递归定义：

• 如果当前节点区间 $[L,R]$ 完全包含于 $[a,b]$，返回1
• 否则，返回 $cover_{\text{左}}(a,b) + cover_{\text{右}}(a,b)$

因此，总贡献 $T(n)$ 可以递归计算。

设 $T(n)$ 表示区间长度为 $n$ 时的答案（即所有子区间的 $cover$ 之和）。

考虑根节点 $[1,n]$，中点 $m = \lfloor (n+1)/2 \rfloor$

将查询区间 $[a,b]$ 分类：

1. 完全在左子树：$1 \leq a \leq b \leq m$

   • 贡献：$T(m)$

2. 完全在右子树：$m+1 \leq a \leq b \leq n$

   • 贡献：$T(n-m)$

3. 跨越中点：$a \leq m < b$

   • 设 $a \in [1, m]$，$b \in [m+1, n]$
   • 对于这样的查询，根节点不会被选中（因为区间不完全包含根节点），而是递归查询左右子树
   • 贡献：$cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)$

计算跨越中点的贡献

对于固定的 $a \in [1,m]$ 和 $b \in [m+1,n]$：

$$cover([a,b]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b) $$

其中 $cover_{\text{左}}(a,m)$ 是在左子树中覆盖 $[a,m]$ 的节点数，$cover_{\text{右}}(m+1,b)$ 类似。

所以跨越中点的总贡献为：

$$\sum_{a=1}^m \sum_{b=m+1}^n [cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)] $$$$= \sum_{a=1}^m \sum_{b=m+1}^n cover_{\text{左}}(a,m) + \sum_{a=1}^m \sum_{b=m+1}^n cover_{\text{右}}(m+1,b) $$$$= (n-m) \cdot \sum_{a=1}^m cover_{\text{左}}(a,m) + m \cdot \sum_{b=m+1}^n cover_{\text{右}}(m+1,b) $$

但 $\sum_{a=1}^m cover_{\text{左}}(a,m)$ 不是 $T(m)$！因为 $T(m)$ 是 $\sum_{1\leq a \leq b \leq m} cover(a,b)$，而这里我们只求和 $a=1$ 到 $m$，$b$ 固定为 $m$。

实际上，$\sum_{a=1}^m cover_{\text{左}}(a,m)$ 表示：在左子树中，所有以右端点 $m$ 结尾的区间的 $cover$ 之和。

类似地，$\sum_{b=m+1}^n cover_{\text{右}}(m+1,b)$ 表示：在右子树中，所有以左端点 $m+1$ 开头的区间的 $cover$ 之和。

定义辅助函数

设：

• $L(n) = \sum_{a=1}^n cover([a,n])$：所有以 $n$ 结尾的区间的 $cover$ 之和
• $R(n) = \sum_{b=1}^n cover([1,b])$：所有以 $1$ 开头的区间的 $cover$ 之和
• $T(n) = \sum_{1\leq a \leq b \leq n} cover([a,b])$：所有区间的 $cover$ 之和

由对称性，$L(n) = R(n)$，因为线段树的结构对称。

递推关系

对于区间 $[1,n]$，中点 $m = \lfloor (n+1)/2 \rfloor$

1. 完全在左：贡献 $T(m)$
2. 完全在右：贡献 $T(n-m)$
3. 跨越中点：
   • 对于每个 $a \in [1,m]$ 和 $b \in [m+1,n]$：$$cover([a,b]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b) $$
   • 总贡献：$\sum_{a=1}^m \sum_{b=m+1}^n [cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)]$
   • $= (n-m) \cdot L_{\text{左}}(m) + m \cdot R_{\text{右}}(n-m)$

其中 $L_{\text{左}}(m)$ 是在左子树中所有以 $m$ 结尾的区间的 $cover$ 之和，$R_{\text{右}}(n-m)$ 是在右子树中所有以 $m+1$ 开头的区间的 $cover$ 之和。

由于左右子树结构与原树类似，只是区间范围不同，$cover$ 函数只依赖于区间长度，所以：

• $L_{\text{左}}(m) = L(m)$
• $R_{\text{右}}(n-m) = R(n-m) = L(n-m)$

因此跨越中点贡献：$(n-m) \cdot L(m) + m \cdot L(n-m)$

所以：

$$T(n) = T(m) + T(n-m) + (n-m) \cdot L(m) + m \cdot L(n-m) $$

还需要 $L(n)$ 的递推。

$L(n)$ 的递推

$L(n) = \sum_{a=1}^n cover([a,n])$

考虑区间 $[1,n]$，中点 $m = \lfloor (n+1)/2 \rfloor$

对于查询区间 $[a,n]$：

• 如果 $a \leq m$：区间跨越中点，$cover([a,n]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,n)$
• 如果 $a > m$：区间完全在右子树，$cover([a,n]) = cover_{\text{右}}(a,n)$

所以：

$$L(n) = \sum_{a=1}^m [cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,n)] + \sum_{a=m+1}^n cover_{\text{右}}(a,n) $$

其中：

• $\sum_{a=1}^m cover_{\text{左}}(a,m) = L(m)$
• $\sum_{a=1}^m cover_{\text{右}}(m+1,n) = m \cdot cover_{\text{右}}(m+1,n)$
• $\sum_{a=m+1}^n cover_{\text{右}}(a,n) = L_{\text{右}}(n-m)$

但 $cover_{\text{右}}(m+1,n)$ 是在右子树中覆盖 $[m+1,n]$ 的节点数，即 $cover([m+1,n])$，而 $[m+1,n]$ 是整个右子树区间，所以 $cover_{\text{右}}(m+1,n) = 1$（整个区间对应一个节点）。

因此：

$$L(n) = L(m) + m \cdot 1 + L(n-m) = L(m) + L(n-m) + m $$

总结递推公式

对于 $n \geq 1$，设 $m = \lfloor (n+1)/2 \rfloor$：

1. $L(1) = 1$（只有区间 $[1,1]$，$cover=1$）
2. $L(n) = L(m) + L(n-m) + m$

对于 $T(n)$：

1. $T(1) = 1$（只有区间 $[1,1]$，$cover=1$）
2. $T(n) = T(m) + T(n-m) + (n-m) \cdot L(m) + m \cdot L(n-m)$

其中 $m = \lfloor (n+1)/2 \rfloor$

验证小例子

$n=1$：

• $L(1)=1$
• $T(1)=1$

$n=2$：

• $m = \lfloor (2+1)/2 \rfloor = \lfloor 1.5 \rfloor = 1$
• $L(2) = L(1) + L(1) + 1 = 1+1+1=3$ 检查：区间 $[1,2]$: $cover=1$，$[2,2]$: $cover=1$，总和 $1+1=2$？不对，$L(2)=\sum_{a=1}^2 cover([a,2]) = cover([1,2]) + cover([2,2]) = 1+1=2$，公式给出3，错误。

问题：$cover([1,2])$ 在长度为2的线段树中是多少？ 线段树：根 $[1,2]$，左 $[1,1]$，右 $[2,2]$

• $cover([1,2])$：根节点完全包含，所以为1
• $cover([2,2])$：叶节点，为1

所以 $L(2)=2$，不是3。

让我们重新推导 $L(n)$。

重新推导 $L(n)$

$L(n) = \sum_{a=1}^n cover([a,n])$

考虑线段树根节点 $[1,n]$，中点 $m = \lfloor (n+1)/2 \rfloor$

对于 $a$ 的取值：

情况1：$a \leq m$

• 查询区间 $[a,n]$ 跨越中点
• $cover([a,n]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,n)$
• $cover_{\text{右}}(m+1,n)$：由于 $[m+1,n]$ 是整个右子树区间，所以等于1

所以对于 $a \leq m$：$cover([a,n]) = cover_{\text{左}}(a,m) + 1$

情况2：$a > m$

• 查询区间 $[a,n]$ 完全在右子树
• $cover([a,n]) = cover_{\text{右}}(a,n)$

因此：

$$L(n) = \sum_{a=1}^m [cover_{\text{左}}(a,m) + 1] + \sum_{a=m+1}^n cover_{\text{右}}(a,n) $$$$= \sum_{a=1}^m cover_{\text{左}}(a,m) + m + \sum_{a=m+1}^n cover_{\text{右}}(a,n) $$

现在：

• $\sum_{a=1}^m cover_{\text{左}}(a,m) = L_{\text{左}}(m) = L(m)$
• $\sum_{a=m+1}^n cover_{\text{右}}(a,n) = L_{\text{右}}(n-m) = L(n-m)$

所以：

$$L(n) = L(m) + L(n-m) + m$$

但验证 $n=2$：

• $m = \lfloor (2+1)/2 \rfloor = 1$
• $L(2) = L(1) + L(1) + 1 = 1+1+1=3$
• 但实际 $L(2)=2$

矛盾。问题在于：对于 $a=1$，$cover([1,2]) = 1$（根节点），但公式给出 $cover_{\text{左}}(1,1) + 1 = cover([1,1]) + 1 = 1+1=2$，错误。

错误原因：当 $a=1$ 时，区间 $[1,2]$ 完全包含根节点，所以 $cover([1,2]) = 1$，不应该递归到左右子树。

所以需要修正：当 $a=1$ 时，区间 $[1,n]$ 完全包含根节点，$cover([1,n]) = 1$，不递归。

修正递推

对于 $L(n) = \sum_{a=1}^n cover([a,n])$：

特殊情况：$a=1$ 时，$cover([1,n]) = 1$

对于 $a \geq 2$：

• 如果 $a \leq m$：$cover([a,n]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,n)$ 由于 $[m+1,n]$ 是整个右子树，$cover_{\text{右}}(m+1,n)=1$ 所以 $cover([a,n]) = cover_{\text{左}}(a,m) + 1$
• 如果 $a > m$：$cover([a,n]) = cover_{\text{右}}(a,n)$

因此：

$$L(n) = 1 + \sum_{a=2}^m [cover_{\text{左}}(a,m) + 1] + \sum_{a=m+1}^n cover_{\text{右}}(a,n) $$$$= 1 + \sum_{a=2}^m cover_{\text{左}}(a,m) + (m-1) + \sum_{a=m+1}^n cover_{\text{右}}(a,n) $$

现在：

• $\sum_{a=2}^m cover_{\text{左}}(a,m) = L(m) - cover_{\text{左}}(1,m)$ 但 $cover_{\text{左}}(1,m) = 1$（在左子树中，区间 $[1,m]$ 是整个区间） 所以 $\sum_{a=2}^m cover_{\text{左}}(a,m) = L(m) - 1$
• $\sum_{a=m+1}^n cover_{\text{右}}(a,n) = L(n-m)$

因此：

$$L(n) = 1 + (L(m)-1) + (m-1) + L(n-m) = L(m) + L(n-m) + m - 1 $$

验证 $n=2$：

• $m=1$
• $L(2) = L(1) + L(1) + 1 - 1 = 1+1+0=2$，正确。

验证 $n=3$：

• $m = \lfloor (3+1)/2 \rfloor = 2$
• $L(3) = L(2) + L(1) + 2 - 1 = 2 + 1 + 1 = 4$ 检查：区间 $[1,3]$: $cover=1$，$[2,3]$: $cover=2$，$[3,3]$: $cover=1$，总和 $1+2+1=4$，正确。

$T(n)$ 的修正递推

$T(n) = \sum_{1\leq a \leq b \leq n} cover([a,b])$

考虑根节点 $[1,n]$，中点 $m = \lfloor (n+1)/2 \rfloor$

分类：

1. 区间完全在左：$1 \leq a \leq b \leq m$，贡献 $T(m)$
2. 区间完全在右：$m+1 \leq a \leq b \leq n$，贡献 $T(n-m)$
3. 区间跨越中点：$a \leq m < b$

对于跨越中点的区间 $[a,b]$：

• 如果 $a=1$ 且 $b=n$：$cover([1,n]) = 1$
• 否则：$cover([a,b]) = cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)$

所以跨越中点贡献：

$$\text{贡献} = 1 + \sum_{a=1}^m \sum_{b=m+1}^n [cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)] - [cover_{\text{左}}(1,m) + cover_{\text{右}}(m+1,n)] $$

最后减去的是 $a=1,b=n$ 的情况，因为我们已经单独计算了 $cover([1,n])=1$。

但 $cover_{\text{左}}(1,m)=1$，$cover_{\text{右}}(m+1,n)=1$，所以：

$$\text{跨越中点贡献} = 1 + \sum_{a=1}^m \sum_{b=m+1}^n [cover_{\text{左}}(a,m) + cover_{\text{右}}(m+1,b)] - 2 $$

计算：

$$\sum_{a=1}^m \sum_{b=m+1}^n cover_{\text{左}}(a,m) = (n-m) \cdot \sum_{a=1}^m cover_{\text{左}}(a,m) = (n-m) \cdot L(m) $$$$\sum_{a=1}^m \sum_{b=m+1}^n cover_{\text{右}}(m+1,b) = m \cdot \sum_{b=m+1}^n cover_{\text{右}}(m+1,b) $$

但 $\sum_{b=m+1}^n cover_{\text{右}}(m+1,b) = L(n-m)$

所以：

$$\text{跨越中点贡献} = 1 + (n-m) \cdot L(m) + m \cdot L(n-m) - 2 $$$$= (n-m) \cdot L(m) + m \cdot L(n-m) - 1$$

因此：

$$T(n) = T(m) + T(n-m) + (n-m) \cdot L(m) + m \cdot L(n-m) - 1 $$

验证 $n=2$：

• $m=1$
• $T(2) = T(1) + T(1) + (2-1)\cdot L(1) + 1\cdot L(1) - 1 = 1+1+1\cdot1+1\cdot1-1 = 1+1+1+1-1=3$ 检查：区间 $[1,1]$:1，$[2,2]$:1，$[1,2]$:1，总和3，正确。

验证 $n=3$：

• $m=2$
• $L(1)=1, L(2)=2$
• $T(3) = T(2) + T(1) + (3-2)\cdot L(2) + 2\cdot L(1) - 1 = 3+1+1\cdot2+2\cdot1-1=3+1+2+2-1=7$ 与样例一致。

最终算法

我们需要计算：

$$T(n) = \sum_{1\leq a \leq b \leq n} cover(a,b)$$

递推公式： 对于 $n \geq 1$，设 $m = \lfloor (n+1)/2 \rfloor$

1. $L(1) = 1$

   $$L(n) = L(m) + L(n-m) + m - 1$$

2. $T(1) = 1$

   $$T(n) = T(m) + T(n-m) + (n-m) \cdot L(m) + m \cdot L(n-m) - 1 $$

由于 $n$ 可达 $10^{18}$，不能直接递归计算。但注意到 $m$ 和 $n-m$ 大约是 $n/2$，递归深度为 $O(\log n)$。

我们可以用记忆化搜索（递归+哈希表）计算，状态数是 $O(\log n)$ 级别。

模运算

所有计算在模 $10^9+7$ 下进行。

由于 $n$ 很大，计算 $(n-m) \cdot L(m)$ 时需要先取模。

注意：$n$ 本身需要取模 $10^9+7$ 吗？在公式中 $n$ 出现在 $(n-m)$ 和 $m$ 中，这些是系数，需要取模。

但 $m = \lfloor (n+1)/2 \rfloor$ 也需要在模意义下计算吗？$m$ 是整数除法，可以在普通整数下计算，然后取模。

由于 $n$ 很大，我们需要处理大整数运算。

复杂度分析

• 递归深度：$O(\log n)$
• 状态数：$O(\log n)$（每个不同的 $n$ 值）
• 每次计算 $O(1)$
• 总复杂度：$O(T \log n)$，对于 $T=1000$，$n=10^{18}$，完全可行。

总结

关键步骤：

1. 定义 $L(n)$ 和 $T(n)$ 的递推关系
2. 通过分析线段树查询过程得到递推公式
3. 使用记忆化搜索高效计算
4. 注意模运算和大整数处理

递推公式：

• $L(1) = 1$
• $L(n) = L(\lfloor \frac{n+1}{2} \rfloor) + L(n - \lfloor \frac{n+1}{2} \rfloor) + \lfloor \frac{n+1}{2} \rfloor - 1$
• $T(1) = 1$
• $T(n) = T(\lfloor \frac{n+1}{2} \rfloor) + T(n - \lfloor \frac{n+1}{2} \rfloor) + (n - \lfloor \frac{n+1}{2} \rfloor) \cdot L(\lfloor \frac{n+1}{2} \rfloor) + \lfloor \frac{n+1}{2} \rfloor \cdot L(n - \lfloor \frac{n+1}{2} \rfloor) - 1$

所有运算对 $10^9+7$ 取模。