线段树（SegmentTree）如何高效处理区间查询问题？

本文共计2014个文字，预计阅读时间需要9分钟。

关于数组的区间染色实现为On，而线段树为O(logn)+。什么是线段树：对于一个二叉树，每个节点存储的是一段连续的区间或相应的信息。在线段树中，每个节点存储的信息可能是区间的最大值、最小值或者是一个操作的结果。查询、更新等操作的时间复杂度通常是O(logn)。

• 对于数组应用于区间染色实现为On，而线段树是O(logn)

• 什么是线段树：对于一个二叉树，每一个节点存储的是一个线段或是一个区间相应的信息。