数组实现的 查询复杂度 不应该是O(1)吗， 只是从sum中取出已经存好的值， 然后做减法， 为什么会是O（n）

Answer 1

liuyubobobo 2020-08-09 17:34:47

抱歉，你具体在讲哪个操作为什么是 O(n)？

• 提问者 追风筝的人or #1

  用数组实现的线段树的查询， 9-6 11分28秒， 上边说是O(n)的复杂度， 我理解的是O（1）， 求大佬解惑

• liuyubobobo 回复 提问者 追风筝的人or #2

  理解了。你估计说的是用 prefix sum 的思想。是的，如果用 prefix sum，是 O(1) 的。我默认使用的数组中存储的是原始数据。

• 提问者 追风筝的人or #3

  明白了  谢谢，

点开查看后面1条评论

Answer 2

提问者 追风筝的人or 2020-08-09 17:44:40

这里不应该是O（1）吗， 因为数组里已经把每个range的和 存好了鸭， 就是取出来就好了嘛

Answer 3

提问者 追风筝的人or 2020-08-09 17:43:54

这个图啊