Algorithm

线段树

线段树是一颗完全二叉树，用于高效地存储区间信息，支持区间查询和区间更新操作。线段树的每个节点代表一个区间，叶子节点代表单个元素

数组元素长度 n = 5 时，线段树结构如下：
             [0,4]
            /     \
       [0,2]       [3,4]
       /   \       /   \
   [0,1]  [2,2] [3,3]  [4,4]
   /   \
[0,0] [1,1]

• 线段树使用了递归和分治的思想，将大区间不断划分为小区间，直到划分到单个元素
• 线段树是一颗完全二叉树，可以用满二叉树的节点数量来近似表示线段树的节点数量，满二叉树节点数量为 2 ** height - 1，叶子节点数量 2 ** (height - 1) >= n，线段树空间大小可近似为 2 * 2 ** height，即 2 * (n).bit_length()，工程上常用 4 * n
• 下标从 1 开始，当前节点下标为 index，左子树下标为 index * 2，右子树下标为 index * 2 + 1
• 区间一般使用闭区间，当前区间为[left, right]，左子区间为 [left, mid]，右子区间为 [mid + 1, right]
• 懒更新先传递懒标记，到下一次查询或更新时再进行实际更新

库函数

二分查找

python 标准库 bisect 模块提供了二分查找的功能，常用函数包括：

• bisect_left(a, x): 返回 x 在 a 中的左侧插入位置
• bisect_right(a, x): 返回 x 在 a 中的右侧插入位置