leetcode二维数组-segment-tree:段树

leetcode二维数组为什么要分段树？ 也称为区间树 也称为锦标赛树 用于运行范围总和查询 即给定范围内所有数字的总和 Prefix sum 用于获取范围和查询 如果输入数组不断发生变异，则前缀总和方法效果不佳 当输入频繁发生变异时使用段树 也用于运行范围最小查询 构建 Segment 树 使用归并排序的分区算法将数组划分为片段 分区后，我们将从叶子返回值到父 段树将被构建如下 使用数组存储段树，类似于Heap 构建段树 构造线段树的算法 段树理论 查找范围总和 有三种重叠类型 查找范围和流 查找范围和算法 更新操作 时间复杂度 比较 回顾段树 段树是二叉树 树底层的节点对应数组元素 其他节点包含处理范围查询所需的信息 最小范围查询的段树 在创建段树时获得最小值而不是求和 在运行 range min 查询时使用 minimum 而不是 sum 而不是差异，在运行更新时使用最小值 二维段树 | 子矩阵和 给定一个矩形矩阵 M[0…n-1][0…m-1]，并要求查询找到一些子矩形 M[a…b][e…f] 上的总和/最小值/最大值，如以及修改单个矩阵元素的查询（即 M[x] [y] = p