【文件属性】：
文件名称：leetcode二维数组-segment-tree:段树
文件大小：16.13MB
文件格式：ZIP
更新时间：2021-07-07 03:22:14
系统开源
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
【文件预览】：
segment-tree-master
----assets()
--------segment-tree.png(1.03MB)
--------find-range-sum-algo.png(1.42MB)
--------range-sum-query.png(173KB)
--------construction-flow.png(681KB)
--------overlap-types.png(1.16MB)
--------compare.png(355KB)
--------min-range-segment-tree.png(2MB)
--------time-complexity.png(1.22MB)
--------compare-algo.png(1.68MB)
--------similar-to-heap.png(209KB)
--------update-flow-algo.png(2.07MB)
--------construction-algo.png(514KB)
--------min-range-query.png(72KB)
--------calculate-sum.png(365KB)
--------theory.png(1.57MB)
--------partition.png(277KB)
--------range-min-query.png(72KB)
--------find-range-sum-flow.png(1.64MB)
----SegmentTreeRangeSum.js(3KB)
----README.md(4KB)