观察到线段树每一层最多只有两种长度的区间.
对于一个长度为 \(n\) 的线段树, 我们考察每一层的区间的长度.
- 第一层: 长度为 \(n\).
- 第二层: 长度为 \(\lfloor \frac{n}{2} \rfloor\), 和 \(\lceil \frac{n}{2} \rceil\).
- 第三层: 长度为 \(\lfloor \frac{\lfloor \frac{n}{2} \rfloor}{2} \rfloor\), \(\lfloor \frac{\lceil \frac{n}{2} \rceil}{2} \rfloor\), \(\lceil \frac{\lfloor \frac{n}{2} \rfloor}{2} \rceil\), \(\lceil \frac{\lceil \frac{n}{2} \rceil}{2} \rceil\). \(n\) 为偶数时显然是只有最多两种长度, \(n\) 为奇数时, 令 \(k = n / 2\), 则转化为 \(\lfloor \frac{k}{2} \rfloor\), \(\lfloor \frac{k + 1}{2} \rfloor\), \(\lceil \frac{k}{2} \rceil\), \(\lceil \frac{k + 1}{2} \rceil\), \(k\) 为奇数和 \(k\) 为偶数均只有两种长度, 且相差为 \(1\).
- 第四层及以后易得…
综上, 每一层只有两种长度, 我们维护一层的区间的长度和该长度的区间的 权值和 \(sum\) 和 区间的数量 \(cnt\). 向下迭代直到区间长度为 \(1\) 时停止即可. 迭代次数为 \(O(log(n))\), 每次迭代需要快速幂计算答案, 故总体复杂度为 \(O(log^2(n))\).