Open coderLCJ opened 5 years ago
https://coderlcj.github.io/2019/06/25/RMQ/#more
任务实现一种数据结构，使得它能够在O(logN)时间复杂度内动态维护一段序列：修改一个元素的权值，询问一段区间内的最小(最大)值。说明线段树的每个结点表示一段区间，每个结点的左右儿子为结点表示的区间从中间断开后的左区间和右区间。每个区间记录当前子树的最大(小)值Top[i]。查询[a,b]区间，对于当前结点i,如果[a,b]能够完全覆盖i表示的区间，则直接返回Top[i],否则判断与左右区间是否有
https://coderlcj.github.io/2019/06/25/RMQ/#more
任务实现一种数据结构，使得它能够在O(logN)时间复杂度内动态维护一段序列：修改一个元素的权值，询问一段区间内的最小(最大)值。说明线段树的每个结点表示一段区间，每个结点的左右儿子为结点表示的区间从中间断开后的左区间和右区间。每个区间记录当前子树的最大(小)值Top[i]。查询[a,b]区间，对于当前结点i,如果[a,b]能够完全覆盖i表示的区间，则直接返回Top[i],否则判断与左右区间是否有