thm1]

给定一棵疏树，原始数组的任意前缀和（并由此引申出任意区间和）均可在对数时间内计算得出，且仅需使用活跃节点的值。

证明出人意料的是，在处理前缀查询这种特殊情况时，第 1 节中描述并在 2.1 中实现的原始区间查询算法竟能原封不动地奏效！也就是说，当遇到当前节点的范围完全包含在查询范围内的基准情形时——此时我们会返回当前节点的值——这种情况只会在活跃节点上发生。

首先，根节点本身是活跃的，因此查询整个范围是有效的。接下来，考虑我们在某个节点上并递归到其两个子节点的情形。左子节点总是活跃的，因此我们只需考虑递归到右子节点的情况。右子节点的范围不可能完全包含在查询范围内：由于查询范围总是形如 $[1, j]$ 的前缀，若右子节点的范围完全包含在 $[1, j]$ 内，那么左子节点的范围也必定如此——这意味着父节点的范围（即其子节点范围的并集）也必定完全包含在查询范围内。但在那种情况下，我们会直接返回父节点的值，而不会递归到右子节点。因此，当我们确实递归到一个右子节点时，我们最终可能会返回 0，或者可能进一步递归到它的两个孙子节点，但无论如何，我们绝不会尝试去查看右子节点本身的值。