为什么在段树上返回的范围查询至大多数$ \ lceil \ log_2 {n} \ rceil $节点？

Question

如果数组 $ a [1 \ ldots n] $ 使用每个间隔中设置的段树表示，为什么range查询 $ [l \ ldots r] $ 返回最多 $ \ lceil \ log_2 {n} \ rceil $ 集（或不相交间隔）？

如果读出这个语句，同时阅读这个答案

引用：

使用标准段查找查询范围的不相交覆盖范围 树查询程序。我们得到 $ o（\ log n）$ 脱节节点，unite 谁的Multisets正是查询范围内的数值。 让我们调用那些多项来 $ s_1，\ dots，s_m $ （使用 $ m \ le \ lceil \ log_2 n \ rceil $ ）。

我试图搜索证明，但在任何网站上都找不到它。任何人都可以帮助我证明它吗？

Answer 1

这是基本想法。

让 Dyadic 间隔是表单的间隔 $$ [2 ^ b a，2 ^ b（a + 1）-1] $$ 对于某些整数 $ a，b \ geq 0 $ 。

1. 如果 $ m <2 ^ n $ 那么表单 $ [0，m-1] $ 可以写作大多数 $ n $ dyadic间隔。

证明。展开 $ m $ 作为2的减少权的总和： $$ m= 2 ^ {a_1} + \ cdots + 2 ^ {a_k}。 $$ 然后我们可以写 $$ [0，m-1]= [0,2 ^ {a_1} -1] \ cup [2 ^ {a_1}，2 ^ {a_1} + 2 ^ {a_2} -1] \ cup \ cdots \ cup [2 ^ {a_1} + \ cdots + 2 ^ {a_ {k-1}}，2 ^ {a_1} + \ cdots + 2 ^ {a_k} -1]。 $$

5.如权利要求2。如果 $ 0 \ leq m_1 \ leq m_2 \ leq 2 ^ n $ 那么表单 $ [M_1，M_2-1] $ 可以写作大多数 $ 2n $ dyadic间隔的脱节联合。

证明。 $ m_1 $ 和 $ m_2 $ 是 $ m_1= x0y，m_2= x1z $ ，其中 $ | y |= | z | $ < / span>。让 $ m= x10 ^ {| z |} $ 。使用索取权利要求1，我们可以将 $ [0，m_2-m-1] $ 作为最多 $ n $ 二元间隔。通过 $ m $ 转移这些，我们表示 $ [m，m_2-1] $ 作为一个联盟最多 $ n $ dyadic间隔。同样，使用索取第1个，我们可以表达 $ [0，M-M_1-1] $ 作为最多 $ n $ 二元间隔。转移和反转，我们表达<跨越类=“math-container”> $ [m_1，m-1] $ 作为最多 $ n $ 二元间隔。

（在这两种情况下，人们需要检查移动，并可能反转，保留时间间隔为二元。）