【数据结构】线段树(Segment Tree)

知识野生技术协会2019-03-25 20:33:33
--播放 · --弹幕未经作者授权,禁止转载
-- --
稿件投诉
【题目】给定一个数组arr,数组可能非常大。在程序运行过程中,你可能要做好几次query和update操作: query(arr, L, R) 表示计算数组arr中,从下标L到下标R之间的所有数字的和。 update(arr, i, val) 表示要把arr[i]中的数字改成val。 怎样尽可能快地完成一系列query和update的操作? 线段树可以在花费一些额外空间的情况下,把这两个操作的时间复杂度都控制在O(log(n))。这段视频主要和大家分享线段树的原理和代码实现。
评论
海外留学党一名,目前在新南威尔士大学读博,大家也可以认为我是无业游民。平时爱好讲讲课,录点教学视频。