我知道段树可用于查找 A 的子数组的总和。根据此处的教程，这可以在 O(logn) 时间内完成。
但是我无法证明查询时间确实是 O(logn)。这个链接（和许多其他链接）说我们可以证明在每个级别，处理的最大节点数是 4，因此 O(4logn) == O(logn)。但是我们如何证明这一点，也许通过矛盾？
如果是这样，如果我们将段树用于高维数组的范围和，如何扩展证明？
例如，我可以考虑通过将原始矩阵划分为 4 个象限（类似于线性数组中的减半间隔）来构建一个象限段树来找到子矩阵和，但我无法证明这一点。