线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法,即对结果下取整)直到 L==R 为止。...复杂度O(log2(n))
(2)线段树的区间查询:
线段树能快速进行区间查询的基础是下面的定理:
定理:n>=3时,一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。...这样,在查询[L,R]的统计值的时候,只需要访问不超过个节点,就可以获得[L,R]的统计信息,实现了O(log2(n))的区间查询。...情况四:[L,R]不包括根节点以及根节点的左右子节点。
于是,剩下的层,每层最多两个节点(参考粗略证明中的内容)。
于是[L,R]最多被分解成了个区间,定理成立。...所以,可以在区间修改的时候不下推标记,留到查询的时候再下推。
注意:如果区间修改时不下推标记,那么PushUp函数中,必须考虑本节点的标记。