切片与线段树

Question

bobo,python中的切片和线段树之间有没有什么联系？
我觉得，切片是取出来可连续的值，然后累加即可得到一个区域的值
线段树好像也是差不多的方式得到值吧，只不过用了递归做
度娘不告诉我，特来请教你

Answer 1

liuyubobobo 2018-11-15 10:20:11

没有联系。

切片只是一个语法而已，可以取出一个数组中的“一段数据”。我们可以非常简单的用一个循环封装出Python的切片功能。但，底层的数据结构，依然是数组（在Python中叫列表）。

但是线段树是一个专门的数据结构。要注意，对于线段树这个数据结构来说，我们所操作的元素本身，就是区间！在线段树中，每一个节点存储的是一个区间的信息！因此，我们可以用线段树高效的处理和区间有关的问题。注意体会，这和数组本质其实存储的是“点元素”有本质区别。

当然，虽然数组本质存储的是点元素，我们依然可以用它解决区间问题。（所有的需要线段树解决的问题，都可以用数组解决！但是能不能达到性能要求，就是另外一回事儿了。）

对于你说的在数组中用切片取出一个区域的值，然后相加，这个操作是O(n)的；

使用线段树，这个操作是O(logn)的：）

• 提问者 king_zl #1

  感谢