线段树

基本概念

线段树(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，即整个区间的长度。

基本操作