线段树

基本概念

线段树(segment tree)是一种二叉搜索树,它的每一个结点对应着一个区间 [L, R],叶子结点对应的是一个单位区间,即 L == R。对于一个非叶子结点 [L, R],它的左儿子所表示的区间为 [L, (L + R) / 2],右儿子所表示的区间为 [(L + R) / 2 + 1, R] (也可以用位运算,更快:[L, (L + R) >> 1] 和 [((L + R) >> 1) | 1, R])。根据定义,线段树是一棵平衡二叉树,它的叶子结点数目为 N,即整个区间的长度。

基本操作