区间问题

Question

老师,我想问下,对于你上课说的区间问题
是否可以使用前缀和衍生的技巧,差分数组进行区间的相关操作?
好像时间复杂度更低

Answer 1

liuyubobobo 2020-09-24 18:36:55

前缀和可以快速处理查询问题，但是一旦设计更新，更新前缀和的复杂度就是 O(n) 了。但是线段树的更新操作也是 O(logn) 的。

另外，前缀和只可以处理“和”的问题，使用线段树也可以灵活处理诸如 max, min 等等其他区间上的问题。

继续加油！：）